【Polya】 hdu 3923(SummerIII Y)

#include <iostream>
using namespace std;
typedef long long LL;
const LL mod=1000000007;
LL c,n;LL gcd(LL a,LL b)
{return b==0?a:gcd(b,a%b);///欧几里得扩展算法求最大公约数
}LL power(LL p,LL n)//快速幂运算
{LL ans=1;while(n){if(n&1)ans=ans*p%mod;p=p*p%mod;n/=2;}return ans;
}
LL  exgcd(LL a,LL b,LL &x,LL &y)///扩展欧几里得算法，返回a,b的最大公约数,ax+by=gcd(a,b)，x,y为方程的一组解
{if(b==0){x=1;y=0;return a;}long long d=exgcd(b,a%b,x,y);long long t=x;x=y;y=t-a/b*y;return d;
}int main()
{int t;cin>>t;int cas=1;while(t--){cin>>c>>n;///c---color n---lenthint ans=0;for(LL i=1;i<=n;i++)///循环节个数为gcd(n,i)， 染色方案为  ∑c^gcd(n,i)    其中 i=1,2,3,4,....n{ans+=power(c,gcd(n,i));///旋转的情况ans%=mod;///每一次计算取模一次}///以下为翻转的情况if(n&1)///如果n为奇数ans+=(n*power(c,n/2+1))%mod;elseans+=((n/2*power(c,n/2+1))%mod+(n/2*power(c,n/2))%mod)%mod; ///注意mod的位置 偶数有两种情况ans%=mod;LL x,y;///以下三行求2*n关于mod的逆元。exgcd(2*n,mod,x,y);///此题为模1000000007 是一个素数，因此2*n和它的最大公约数为1，无需再进行判断。///注意：这里的置换群是2*n个///x=power(2*n,mod-2)%mod;//第二种方法x=(x+mod)%mod;///防止出现负数的情况cout<<"Case #"<<cas++<<": "<<ans*x%mod<<endl;}return 0;
}