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 番目以下です。