守护白起
程序员文章站
2022-06-26 17:23:24
最近古yu迷上了《恋与制作人》,天天嚷嚷着白起我老公(死gay死gay的),白起又向古yu提出了一个问题:给你n种卡牌(数量无限),将其摆成长度为m的圆环的方案数。(如果这个环可以通过若干次旋转或者反方向读((abc)(cba)是一样的),则认为他们是一样的)这时古yu一脸茫然,大哭特苦不能守护白起了。古yu希望你能帮助他解决这个问题去守护白起。输入描述:第一行一个t(0
最近古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://blog.csdn.net/qq_44826711/article/details/114241629