这种换来换去的东西很容易想到置换群那一套，然后题目甚至还暗示了二进制=。=
直接换的话显然是$2^{a+b}$次，但是一个循环节里可以少换一次，然后问题就变成了数循环节
在一个循环节里的位置有什么特征？用二进制表示位置，那么他们的位置可以通过循环左移a位/循环右移b位互相表示，然后问题就变成了：在左移a位/右移b位的置换群作用下，在a+b个01构成的环里找等价类。仍然不好做，因为现在直接Burnside做不出来，Polya又还没法做，继续转换
我们把每$gcd(a,b)$个数缩成一个，也就是转成$\frac{(a+b)}{gcd(a,b)}$个环数等价类。这样的好处是旋转都变成了1位，然后套上Polya就可以了，大概需要卡一卡常？
1 #include2 #include 3 #include 4 using namespace std; 5 const int N=1e6+60,mod=1e6+3; 6 int T,a,b,cnt,c1,c2,pwe[10],prf[10]; 7 int pw[N],npr[N],pri[N],mind[N],fac[N],fai[N]; 8 int GCD(int a,int b) 9 {10 return b?GCD(b,a%b):a;11 }12 void Add(int &x,int y)13 {14 x+=y;15 if(x>=mod) x-=mod;16 }17 int Qpow(int x,int k)18 {19 if(k==1) return x;20 int tmp=Qpow(x,k/2);21 return k%2?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod;22 }23 void Pre()24 {25 npr[1]=true,mind[1]=1;26 for(int i=2;i<=1000000;i++)27 {28 if(!npr[i]) pri[++cnt]=i,mind[i]=i;29 for(int j=1,k;j<=cnt&&(k=i*pri[j])<=1000000;j++)30 {31 npr[k]=true,mind[k]=pri[j];32 if(i%pri[j]==0) break;33 }34 }35 pw[0]=1;36 for(int i=1;i<=1000000;i++)37 pw[i]=pw[i-1]*2%mod;38 }39 void DFS(int idx,int num,int phi)40 {41 if(idx>c2)42 fac[++c1]=num,fai[num]=phi;43 else44 {45 int pr=prf[idx];46 DFS(idx+1,num,phi);47 DFS(idx+1,num*=pr,phi*=pr-1);48 for(int i=2;i<=pwe[idx];i++)49 DFS(idx+1,num*=pr,phi*=pr);50 }51 }52 void Decompose(int x)53 {54 if(x==1)55 fac[c1=1]=1;56 else57 {58 c2=0;59 while(x!=1)60 {61 prf[++c2]=mind[x],pwe[c2]=0;62 while(x%prf[c2]==0) x/=prf[c2],pwe[c2]++;63 }64 c1=0,DFS(1,1,1);65 }66 }67 int Query(int len,int col)68 {69 int ret=0;70 Decompose(len);71 for(int i=1;i<=c1;i++)72 Add(ret,1ll*fai[len/fac[i]]*Qpow(col,fac[i])%mod);73 return 1ll*ret*Qpow(len,mod-2)%mod;74 }75 int main()76 {77 Pre();78 scanf("%d",&T);79 while(T--)80 {81 scanf("%d%d",&a,&b);82 if(!a||!b) puts("0");83 else84 {85 int g=GCD(a,b);86 printf("%d\n",(pw[a+b]-Query((a+b)/g,pw[g])+mod)%mod);87 }88 }89 return 0;90 }