← 返回题目列表

AtCoder · joisc2007_fermat

fermat. 费马方程(Fermat)

中文机器翻译题面 查看原题

以下是来自日本的原始新闻PDF,已完整保存和染色。

フェルマー方程式 (Fermat) - 原题 PDF 第 1 页
原题PDF第3页
可复制的 PDF 提取文本
Fermat: フェルマー方程式


input ファイル“fermat.in”
output 標準出力
ソースファイルfermat.c/fermat.cpp/Fermat.java
時間制限0.5 秒/ データ


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

                               xn + yn ≡zn  (mod p)

をみたす整数x, y, z (0 ≦x, y, z ≦p −1) の組(x, y, z) の個数m を求めるプログラムを作れ.こ

こで,a ≡b  (mod p) とは,a −b がp で割り切れることを意味する.

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

は自然数n (1 ≦n ≦10000) が書かれている.

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

例1
 fermat.in 標準出力
 3          9
 5


  x5 + y5 ≡z5  (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
 fermat.in 標準出力
 19         487
 21


  x21 + y21 ≡z21  (mod 19) をみたす整数x, y, z (0 ≦x, y, z ≦18) の組(x, y, z) は487 個ある.

注意採点に用いる入力データに対しては,m の値は231 よりも小さい.


                   フェルマー方程式–1/1