最近古yu迷上了《戀與制作人》，天天嚷嚷著白起我老公(死gay死gay的),白起又向古yu提出了一個問題：
給你n種卡牌（數量無限）,將其擺成長度為m的圓環的方案數，
(如果這個環可以通過若干次旋轉或者反方向讀(（abc）(cba)是一樣的),則認為他們是一樣的)
這時古yu一臉茫然，大哭特苦不能守護白起了，古yu希望你能幫助他解決這個問題去守護白起，
輸入描述:
第一行一個t(0<t<=500)
接下來t行，每行倆個正整數n,m(1<=n,m<=10000)
輸出描述:
一個答案加換行(答案可能很大，所以取模1000000007)
示例1
輸入
2
3 4
1 2
輸出
21
1
說明
對于第一個樣例有21種不同的方法
/ aaaa / aaab / aaac / aabb / aabc / aacc / abab /
/ abac / abbb / abbc / abcb / abcc / acac / acbc /
/ accc / bbbb / bbbc / bbcc / bcbc / bccc / cccc
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
int phi[10005];
bool isp[10005];
int pri[10005],cnt=0;
inline void getp()
{
phi[1]=1;
for (int i=2;i<=10000;i++)
{
if (!isp[i]) {pri[++cnt]=i;phi[i]=i-1;}
for (int j=1;i*pri[j]<=10000&&j<=cnt;j++)
{
isp[i*pri[j]]=1;
phi[i*pri[j]]=phi[i]*(pri[j]-1);
if (i%pri[j]==0) {phi[i*pri[j]]=phi[i]*pri[j];break;}
}
}
}
inline int qpow(int a,int b)
{
int res=1,tp=a;
while (b)
{
if (b&1) res=1ll*res*tp%mod;
tp=1ll*tp*tp%mod;b>>=1;
}
return res;
}
int main()
{
getp();
int test,n,m;
scanf ("%d",&test);
while (test--)
{
scanf ("%d%d",&m,&n);
int ans=0;
for (int i=1;i*i<=n;i++)
{
if (n%i==0)
{
ans+=1ll*phi[n/i]*qpow(m,i)%mod;
if (ans>=mod) ans-=mod;
if (i*i!=n)
{
ans+=1ll*phi[i]*qpow(m,n/i)%mod;
if (ans>=mod) ans-=mod;
}
}
}
if (n&1) {ans+=1ll*n*qpow(m,n/2+1)%mod;}
else {ans+=1ll*(n/2)*(qpow(m,n/2)+qpow(m,n/2+1))%mod;}
ans=1ll*ans*qpow(2*n,mod-2)%mod;
printf ("%d\n",ans);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/265405.html
標籤：其他