var
  m,i,j,p,t,ti,l:longint;
  n,s,a,b:int64;
  w:array[1..30000] of int64;
  f:array[0..30000] of boolean;
  flag:boolean;
begin
  readln(t);
  for ti:=1 to t do
    begin
      readln(m,p);
      n:=m;
      w[1]:=1 mod p;
      l:=1;
      fillchar(f,sizeof(f),false);
      flag:=false;
      repeat
        inc(l);
        w[l]:=(w[l-1]*(n mod p)) mod p;
        j:=w[l];
        if f[j] then
          begin
            flag:=true;
            break;
          end;
        f[j]:=true;
      until l=m;
      if flag then
        begin
          dec(l);
          for i:=1 to l do
            if w[i]=w[l+1] then break;
          for j:=i to l do w[j-i+1]:=w[j];
          l:=l-i+1;
          s:=w[((m-i) mod l+1)];
        end
              else s:=w[m];
      if odd(n) then
        begin
          a:=1 mod p;
          b:=(n-1) mod p;
          s:=(s+a*b) mod p;
        end
                else
        begin
          a:=n mod p;
          b:=(n div 2) mod p;
          s:=(s+b) mod p;
          b:=(n div 2-1) mod p;
          s:=(s+(a mod p)*b) mod p;
        end;
      writeln(s);
    end;
end.

• 是O(XP)的Polya (1274) JiangLY 2005-07-25 18:48:08
  • Polay部分最高复杂度为O(P),有X组数据，所以总复杂度为O(XP)，还能怎样优化？ (0) JiangLY 2005-07-25 18:52:07
    • 是O(ps)吧 (0) frkstyc 2005-07-25 18:53:14
      • 为什么？ (0) JiangLY 2005-07-25 18:55:53
        • lrj书上写的 (0) frkstyc 2005-07-25 18:57:04
          • 我是说这道题，我从N^2优化到P，不行了…… (0) JiangLY 2005-07-25 18:59:45
            • 大牛帮忙~ (0) JiangLY 2005-07-25 19:06:41
              • __int64 TLE int AC (0) swust20064469 2009-07-12 19:06:20
                • 为什么呢？我也一样，虽然效率不高。 (0) 10070709 2009-08-08 21:46:34
• 这算法正确性有问题吧？ (49) Zenomyth 2013-12-24 11:02:32