题意：
给出a、b 表示按先行后列的方式储存矩阵 现在要将其转置 可以交换两个点的位置 求最小操作次数
题解：
储存可以将其视为拉成一条链 设a=5、b=2 则在链上坐标用2^***(a,b)表示为(xxxxxyy) 转置后为(yyxxxxx)
这时将其视为另一个点的坐标 继续转置为(xxyyxxx)... 直到再变成(xxxxxyy)这样每次循环可以节省1次转置 所以ans=2^(a+b)-k k为循环的个数
k的计算：右移b位 右移b*2位 右移b*3位... 构成了一个置换群 置换个数为(a+b)/***(a，b)
因为它是循环的 所以向右移bx位 可视为右移bx%(a+b)位 设bx=z(mod (a+b))
该方程有解条件为***(b，(a+b))|z -> ***(a，b)|z 所以z为***(a，b)的倍数
k的值可理解为将长度为(a+b)/***(a，b)的串 染成2^***(a，b)种颜色(循环移动视为同种方案) 的方案数
既为poj2154的题目
因为spoj会卡常数 这题很容易TLE 我做了几个优化：
1.记忆化欧拉函数 将算过的欧拉函数存下来 下次直接用
2.预处理幂 可以发现这题要用的幂都是2^x 可以直接预处理出来
3.dfs n的因数 枚举m的因数会浪费很多时间 可以先算出n的质因数 在通过dfs算出其因数
4.尽量不要用long long 在会超int的地方强制转换一下就行
这题时限是8s 我跑了4.2s 目测前面T了十几次
代码：
#include <cstdio>
#define _(x) static_cast<long long>(x)
const int mo=;
typedef int ll;
ll t,a,b,n,m,g,phii[],primer[],np,flag[],pow[],ans,p[],nn;
void makep(ll t){
for (int i=;i<=np && t> && primer[i]*primer[i]<=t;i++)
if (t%primer[i]==){
p[++nn]=primer[i];
while (t%primer[i]==) t/=primer[i];
}
if (t>) p[++nn]=t;
}
ll phi(ll t){
ll out=,tt=t;
if (phii[t]) return phii[t];
for (int i=;i<=np && t> && primer[i]*primer[i]<=t;i++)
if (t%primer[i]==){
t/=primer[i];
out=_(out)*_((primer[i]-))%mo;
while (t%primer[i]==) t/=primer[i],out=_(out)*_(primer[i])%mo;
}
if (t>) out=_(out)*_((t-))%mo;
return phii[tt]=out;
}
void dfs(ll now,ll sum){
if (now>nn){
ans=(ans+_(phi(n/sum))*_(pow[sum*g]))%mo;
return;
}
for (ll i=;n%i==;i*=p[now]) dfs(now+,sum*i);
}
void extgcd(ll a,ll b,ll &x,ll &y){
if (!b) x=,y=;
else{
extgcd(b,a%b,x,y);
ll t=x;
x=y;
y=t-a/b*y;
}
}
ll gcd(ll a,ll b){
while (b) b^=a^=b^=a%=b;
return a;
}
ll work(){
if (!a || !b) return ;
ll x,y;
g=gcd(a,b);
n=(a+b)/g;
nn=ans=;
makep(n);
dfs(,);
extgcd(n,mo,x,y);
x=(x%mo+mo)%mo;
ans=(_(ans)*_(x))%mo;
return ((pow[a+b]-ans)%mo+mo)%mo;
}
void makepr(){
for (int i=;i<=;i++){
if (!flag[i]) primer[++np]=i;
for (int j=;j<=np && primer[j]*i<=;j++){
flag[primer[j]*i]=;
if (i%primer[j]==) break;
}
}
pow[]=;
for (int i=;i<=;i++) pow[i]=(pow[i-]*)%mo;
}
int main(){
freopen("spoj442.in","r",stdin);
freopen("spoj442.out","w",stdout);
scanf("%d\n",&t);
makepr();
while (t--){
if (t==){
t=;
}
scanf("%d%d\n",&a,&b);
printf("%d\n",work());
}
fclose(stdin);
fclose(stdout);
}