欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

守护白起

程序员文章站 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