題名からして素因数分解するのは間違いないとして、約数の積が何通り作れるかを考えるのだが… 頭が固くて自力では解けなかった。解説AC 例えば n=4 , m=360 (2^3*3^2*5^1) とすると答えとなるものは A1*A2*A3*A4 = 360 となるものであるが、 A1 は 360の約数…

素数についての謎の知識を二つ得た 1. p が素数のとき、x^n % p = x^(n%(p-1)) % p 2. p-1 > c > 1 のとき、x^n+y^n≡c (mod p) を満たす個数は０または x^n+y^n≡1 (mod p) を満たす個数に等しい。 証明はここをみてください。 フェルマー方程式/Fermat(JOI20…

10**5までの素数のリストをどう作るのが早いかという話。 とりあえず python 素数判定 高速 でググってこれをコピペしてみた。ミラーテストというらしい。 Pythonを使って高速素数判定をしてみる - Pashango’s Blog k = 13 のときで 1700ms だった。 4**13分…