12の約数は 1,2,3,4,6,12 である。このうち12の平方根を超えない最大の数は3である。
整数 n に対し，その平方根を超えないような n の最大の約数を n の擬似平方根(PSR) と呼ぶことにしよう。PSR(3102)=47 である。p を 190 未満の素数の積とする。
PSR(p) mod 10^16 を求めよ。
PSR[n] を求める関数は Mathematica で簡単に書けますが，2^42 個もの約数についてまともに調べるのは流石に無理でした。メモリ不足で止ってしまいます。
PSR[n_]:=Max[Select[Divisors[n], #^2 <= n &]]
190以下の素数42個を小さい方から順に1個目～21個目，22個目～42個目の2グループに分け，その積の約数を求めます。これら約数の集合を小グループ，大グループとよぶことにします。
求める数は小グループの数1個と大グループの数1個の積です。
- 小グループの数を1個選んで固定
- 積が √p を超えないように，ペアになる大グループの数を選ぶ
- すべてのペアの積の最大値が答え
と，このように計算しました。大グループの検索範囲が徐々にせばまっていくことに気づくと，大幅に時間を短縮できます。
たとえば小グループの i 番目が大グループの j 番目とペアになったとすると，小グループの i+1 番目とペアになるのは大グループの j 番目以下です。