var
  f:Array[0..400000] of boolean;
  prime:array[0..100000] of longint;
  seq:array[0..100,1..3] of longint;
  n,md,s,t,i,j,num,k,p,now:longint;
  ans:int64;
function pow(a,b:longint):int64;
  begin
    a:=a mod md;////////////就是这句话
    pow:=1;
    while b>0 do
      begin
      if b and 1=1 then pow:=(pow*a) mod md;
      a:=(a*a) mod md;
      b:=b shr 1;
      end;
  end;
procedure print;
  var
    i,phi:longint;
  begin
    phi:=1;
    for i:=1 to num do
      if seq[i,2]<>0 then phi:=phi*(seq[i,3]-seq[i,3] div seq[i,1]);
    ans:=(ans+(pow(n,n div now-1)*phi) mod md) mod md;
  end;
procedure work(dep:longint);
  var
    i,p,t,tt:longint;
  begin
    if dep>num then begin print; exit; end;
    work(dep+1);
    p:=seq[dep,2];
    t:=seq[dep,3];
    tt:=now;
    for i:=1 to seq[dep,2] do
      begin
      dec(seq[dep,2]);
      seq[dep,3]:=seq[dep,3] div seq[dep,1];
      now:=now div seq[dep,1];
      work(dep+1);
      end;
    seq[dep,2]:=p;
    seq[dep,3]:=t;
    now:=tt;
  end;
procedure getprime;
  var
    i:longint;
  begin
    for i:=2 to trunc(sqrt(1000000000)) do
      if not f[i] then
         begin
         inc(prime[0]);
         prime[prime[0]]:=i;
         j:=2;
         while i*j<=trunc(sqrt(1000000000)) do
           begin
           f[i*j]:=true;
           inc(j);
           end;
         end;
  end;
begin
  getprime;
  readln(t);
  for s:=1 to t do
    begin
    readln(n,md);
    ans:=0;
    num:=0;
    k:=n;
    for i:=1 to prime[0] do
      begin
      if (k<prime[i])or(prime[i]>trunc(sqrt(n))) then break;
      if k mod prime[i]=0 then
         begin
         inc(num);
         seq[num,1]:=prime[i];
         seq[num,2]:=0;
         seq[num,3]:=k;
         while k mod prime[i]=0 do
           begin
           inc(seq[num,2]);
           k:=k div prime[i];
           end;
         seq[num,3]:=seq[num,3] div k;
         end;
      end;
    if k>1 then begin inc(num); seq[num,1]:=k; seq[num,2]:=1; seq[num,3]:=k; end;
    now:=n;
    work(1);
    writeln(ans);
    end;
end.

• Re:一定要对n取模，我就是这样wa了好几次 (12) weligo 2022-03-11 13:13:39