#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---lenth
int 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;
else
ans+=((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;
}参考网站：
点击打开链接
