这题目就比较有趣了。
大概题目中介绍了一下计算机的储存方法，给一个$2^a*2^b$的矩阵。
求转置。但是只能交换两个数，求所需要的步数。
首先可以把变化前后的位置写出来，构成了许多的循环。左转将狼踩尽博客
然后就是求循环的个数了。
发现循环都是左移形成的，可以直接计算本质不同的串的个数。
（这里用到一个小优化，把最小的循环节找出来可以简化问题，这样子可以变成循环任意多次，就能用欧拉函数了）
然后就是一顿模板 （POJ2154）
然后交上去
TLE。
SPOJ太慢了
1s跑不过40w的$nsqrt(n)$
然后把2的幂次预处理出来，然后吧逆元线性递推。还是TLE。
然后去看别人的博客，讲了一种奇怪的做法，然而我并没有看懂是什么情况。
也没有任何人讲到。
那看看算法主体中哪些地方还可以优化。
然后怒用调和级数处理因子，然后把vector换成了邻接表，然后A掉了。
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 1000005
int pri[maxn],top,phi[maxn],vis[maxn];
int pw[maxn<<2],inv[maxn]; #define ll long long
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i) int h[maxn*20],to[maxn*20],ne[maxn*20],en=0; void add(int a,int b)
{
to[en]=b;ne[en]=h[a];h[a]=en++;
} inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){
char c=nc(),b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
} int t,a,b,d,c,p=1000003,e; void Shaker()
{
phi[1]=1;
F(i,2,maxn-1)
{
if (!vis[i]) pri[++top]=i,phi[i]=i-1;
for (int j=1;j<=top&&(ll)i*pri[j]<maxn;++j)
{
vis[i*pri[j]]=1;
if (i%pri[j]==0){phi[i*pri[j]]=phi[i]*pri[j];break;}
phi[i*pri[j]]=phi[i]*phi[pri[j]];
}
}
inv[1]=1; F(i,2,maxn-1) inv[i]=(p-(ll)p/i*inv[p%i])%p;
pw[0]=1;
F(i,1,(maxn<<2)-1) pw[i]=pw[i-1]*2%p;
F(i,1,maxn-1)
for (int j=i;j<maxn;j+=i)
add(j,i);
} int ksm(int a,int b)
{
int ret=1;
for (;b;b>>=1,a=(ll)a*a%p) if (b&1) ret=(ll)ret*a%p;
return ret;
} int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);} int main()
{
memset(h,-1,sizeof h);
Shaker();
read(t);
while(t--)
{
int ans=0;
read(a);read(b);
if (a*b==0) {printf("0\n");continue;}
d=gcd(a,b); c=a+b; c=c/d; e=pw[d];
for (register int i=h[c];i>=0;i=ne[i])
ans=(ans+(ll)phi[c/to[i]]*pw[d*to[i]]%p)%p;
ans=(ll)ans*inv[(a+b)/d]%p;
printf("%d\n",((pw[c*d]-ans)%p+p)%p);
}
}