2007-day2-fermat-prob - 情報オリンピック攻略Wiki

フェルマー方程式 (Fermat)

---

時間制限 : 0.5sec / スタック制限 : 64MB / メモリ制限 : 64MB

---

　素数p と自然数n ≧ 1 が与えられたとき，

xⁿ + yⁿ ≡ zⁿ (mod p)

をみたす整数x, y, z (0 ≦ x, y, z ≦ p - 1) の組(x, y, z) の個数mを求めるプログラムを作れ．ここで，a ≡ b (mod p) とは，a - b がp で割り切れることを意味する．

入力

　入力ファイルfermat.in の1行目には素数p (p < 10000) が書かれている．2 行目には自然数n (1 ≦ n ≦ 10000) が書かれている．

出力

　標準出力に1 つの整数mのみからなる1 行を出力せよ．

入出力例

入力例1	出力例1
3 5	9

　x⁵ + y⁵ ≡ z⁵ (mod 3) をみたす整数x, y, z (0 ≦ x, y, z ≦ 2) の組(x, y, z) は

(0,0,0), (0,1,1), (0,2,2), (1,0,1), (1,1,2), (1,2,0), (2,0,2), (2,1,0), (2,2,1)

の9 個である．

入力例2	出力例2
19 21	487

　x²¹ + y²¹ ≡ z²¹ (mod 19) をみたす整数x, y, z (0 ≦ x, y, z ≦ 18) の組(x, y, z) は487 個ある．

注意　採点に用いる入力データに対しては，mの値は2³¹ よりも小さい．

コメント