利用bzoj2705的结论我们很容易优化这道等价类计数的问题
sum(n^gcd(i,n))/n mod p (1<=i<=n)
=sum(phi(n/L)*n^L)/n mod p (n mod L=0)
=sum(phi(n/L)*n^(L-1)) mod p
这题时限略紧,我的pascal怎么都卡不过去,请指教
var b:array[..] of longint;
s,p,i,t,m:longint;
n,ans:longint; function quick(x:longint):longint;
var i,j:longint;
begin
j:=;
while x<> do
begin
inc(j);
b[j]:=x mod ;
x:=x shr ;
end;
quick:=;
for i:=j downto do
begin
quick:=sqr(quick) mod p;
if b[i]= then quick:=quick*m mod p;
end;
end; function phi(x:longint):longint;
var i:longint;
begin
phi:=;
for i:= to trunc(sqrt(x)) do
if x mod i= then
begin
phi:=phi*(i-);
x:=x div i;
while x mod i= do
begin
x:=x div i;
phi:=phi*i;
end;
if x= then break;
end;
if x> then phi:=phi*(x-);
phi:=phi mod p;
end; begin
readln(t);
while t> do
begin
readln(n,p);
m:=n mod p;
ans:=;
for i:= to trunc(sqrt(n)) do
if n mod i= then
begin
ans:=ans+phi(n div i)*quick(i-) mod p;
if i<>n div i then ans:=ans+phi(i)*quick(n div i-) mod p;
ans:=ans mod p;
end;
writeln(ans);
dec(t);
end;
end.