フェルマー方程式/Fermat(JOI2007春合宿Day2 2nd)

春合宿まで精進するぞって言ってし始めたんですが結構始めから躓いていて早速数学に苦しめられています。(本選参加記はもう少ししたら書きます。)
Fermatも理解できず、LatteMaltaさん(@latte0119)に教えていただいてなんとか理解できたので忘れないうちに備忘録としてまとめます。(ありがとうございました！)

@Wp120_3238
x^n+y^n=z^nで、d=z^-1とすると、両辺にdをかけて、(ad)^n+(bd)^n=1となります。(z=1のときの答え)×(p-1)=(z!=0のときの答えの合計)となることを示したくて、(続く)

— ひふみ☆ (@MochaLatvia) 2017年2月16日

問題概要

• 公式PDF
• AtCoderジャッジ
• xⁿ+yⁿ≡zⁿ(mod p)となるx, y, zの組み合わせの数を求める。
• 2<=p<10⁴ pは素数
• 0 <= x, y, z <= p - 1
• 1 <= n <= 10⁴

解法

まずはpで割った余りがaとなるxⁿのxの数をcount[a]など配列に保存しておく必要があります。単純に計算するとO(NP)かかりますが繰り返し二乗法を用いるとO(PlogN)で済みます。(繰り返し二乗法については割愛します。)
xⁿ≡a(mod p), yⁿ≡b(mod p), zⁿ≡c(mod p)となるa, b, c(0 <= a, b, c <= p-1)を置きます。
ここまで考察するとaとbはそれぞれP通りあり、count[a]*count[b]*count[(a+b)%P]を全て足し合わせる解法が浮かびます。
2007年と古い問題であり、制約が10⁴と小さいため上記の方法で行うO(N²)解法が結構ありますが当時はそれでは間に合いません 。

頭の良い人ならすぐにわかるのかもしれませんが私にはわかりませんでした。以下のようなことをしていきます。
c=1の時のx, y, zの組み合わせの個数はc>1の時の解の個数と一致する仮定を立てます。(O(P²)のコードを適当に書きましょう。)
これを証明していきます。

cがtの時のx, y, zの組み合わせの個数をf(t)と置く。
c=1となるとき、xⁿ+yⁿ≡1(mod p)。 c>1となるzをtと置き、tⁿを式全体にかけると、(xt)ⁿ+(yt)ⁿ≡tⁿ(mod p)となります。この式よりzがtとなるとき、少なくとも(xt, yt)の組み合わせが解となります。(x, yはz=1の時の解です。) ここで、t>1においてxt≢x(mod p)かつyt≢y(mod p)であるため、f(1)<=f(t)(t > 1)…(1)。

また、xⁿ+yⁿ≡zⁿ(mod p)においてzとpは互いに素であるからzの逆元をdと置くと(xd)ⁿ+(yd)ⁿ≡1(mod p)であり、(xd,yd)が必ずc=1の解となる。
(x, y)はzⁿの時の解であるため、先程と同様にf(t)<=f(1)(t > 1)…(2)。

(1)(2)よりf(t)=f(1)である。
よって、f(0)+f(1)*(0を除くcの種類の数)で求められる。
コードはAtCoderの提出を参照。

感想

むずい！数学むずすぎるよ！
こんなもん仮定立てて証明までするとかできる気がしないんで本番であったら間違いなく仮定だけしてそうっぽい！wって言って組み始めそう…
というわけで一応まとめてみました。結構急ぎでまとめたので改善点とか結構あると思います。コメントやTwitter等で教えていただけると幸いです。