P≡NP → P(N−1)≡0
と式変形をします.
すると,N−1の範囲は[−1,M−2]になりますが,−1≡M−1 であり,Nは整数であるため,N−1の範囲を[0,M−1]としても問題ありません.よって,N′=N−1とすると,
0≤P,N′<M
PN′≡0
を満たすP,N′の個数を求めてあげればよいです.
ここで, P の値を固定した時に条件を満たす N′の個数を考えます.これは,PとMの最大公約数をgと置くと,N′が(M/g)の倍数の時に与えられた式を満たすため,条件を満たすN′の個数は M/(M/g)=g
個になります.よって,本問題は以下のように言い換えることができます.
- 正整数Mが与えられる.gcd(a,b) を a,bの最大公約数とするとき,
∑k=0M−1gcd(k,M) を求めてください
以降,言い換えた問題を考えます.
M=a×b, gcd(a,b)=1 となるような(a,b)を考えると,
gcd(i,M)=gcd(i,a)×gcd(i,b)
が成り立ちます.この変換を用いると,
∑k=0M−1gcd(k,M)=∑k=0M−1(gcd(k,a)×gcd(k,b))
となります.ここで,gcd(k,a)=gcd(k,a%k) と,中国の剰余定理より「互いに素である (a,b) が a×b=Mを満たすとき,0以上M未満の正整数の中に,各 0≤i<a, 0≤j<b について a で割ると i 余り,b で割ると j 余る数が丁度1つずつ存在する」ことを利用すると,
∑k=0M−1gcd(k,a)×gcd(k,b)
=(gcd(0,a)+gcd(1,a)+⋯+gcd(a−1,a))×(gcd(0,b)+gcd(1,b)+⋯+gcd(b−1,b))
=∑k=0a−1gcd(k,a)×∑k=0b−1gcd(k,b)
を解けば良いことになります.よって,Mが素数pi及び正整数eiを用いて
M=∏piei
と表されるとき,
∏(∑k=0piei−1gcd(k,piei))
が答えになります.
後は,各pi,ei について,∑k=0piei−1gcd(k,piei)の値を求めてあげればよいです.
この答えについては,[0,piei)の範囲内にpieiの倍数が1個,piei−1の倍数がpi個,piei−2の倍数がpi2個 ... ずつあることを利用すると,最大公約数の総和は
piei+∑k=0ei−1pik×(piei−k−piei−k−1)
=piei+ei×(piei−piei−1)
=piei−1×(pi+(pi−1)×ei)
式で計算できます.
よって,各素因数ごとに登場回数を調べ,最後の式で計算される値を掛け合わせることによって,本問題を解くことが出来ます.
計算量は,各素因数ごとに登場回数を数える箇所に依存し,C++ の map 等を使って求めるとO(klogk)に,unordered_map を使ったり入力がソートされた状態で与えられることを利用するなどして登場回数を数えると O(k) になります.
想定解 (C++ with ACL)
想定解 (Python)