poj2154

利用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怎么都卡不过去，请指教

 1 var b:array[0..31] of longint;
 2     s,p,i,t,m:longint;
 3     n,ans:longint;
 4 
 5 function quick(x:longint):longint;
 6   var i,j:longint;
 7   begin
 8     j:=0;
 9     while x<>0 do
10     begin
11       inc(j);
12       b[j]:=x mod 2;
13       x:=x shr 1;
14     end;
15     quick:=1;
16     for i:=j downto 1 do
17     begin
18       quick:=sqr(quick) mod p;
19       if b[i]=1 then quick:=quick*m mod p;
20     end;
21   end;
22 
23 function phi(x:longint):longint;
24   var i:longint;
25   begin
26     phi:=1;
27     for i:=2 to trunc(sqrt(x)) do
28       if x mod i=0 then
29       begin
30         phi:=phi*(i-1);
31         x:=x div i;
32         while x mod i=0 do
33         begin
34           x:=x div i;
35           phi:=phi*i;
36         end;
37         if x=1 then break;
38       end;
39     if x>1 then phi:=phi*(x-1);
40     phi:=phi mod p;
41   end;
42 
43 begin
44   readln(t);
45   while t>0 do
46   begin
47     readln(n,p);
48     m:=n mod p;
49     ans:=0;
50     for i:=1 to trunc(sqrt(n)) do
51       if n mod i=0 then
52       begin
53         ans:=ans+phi(n div i)*quick(i-1) mod p;
54         if i<>n div i then ans:=ans+phi(i)*quick(n div i-1) mod p;
55         ans:=ans mod p;
56       end;
57     writeln(ans);
58     dec(t);
59   end;
60 end.

View Code