> 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.

• 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