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

ACM-ICPC 2018 焦作赛区网络预赛-G-Give Candies

程序员文章站 2022-03-04 21:07:22
...

ACM-ICPC 2018 焦作赛区网络预赛-G-Give Candies

地址:https://nanti.jisuanke.com/t/31716

思路:手算出n=4,5的结果可以发现 答案就是 2^(n-1) ,但是这里的 n<=10^100000就算用快速幂也会超时,因此需要用费马小定理: a^(p-1)=1 (mod p) ,将 n对(MOD-1)取模后-1 ,然后再用快速幂即可

Code :

#include<cstdio>
#include<cstring>
typedef long long LL;

const int MOD=1000000007;
int T;
char str[100005];

int main()
{
	scanf("%d",&T);
	while(T--){
		scanf("%s",str);
		int len=strlen(str);
		LL n=0,mod=MOD-1;
		for(int i=0;i<len;++i)
			n=(n*10+str[i]-'0')%mod;
		n=(n+mod-1)%mod;
		LL ans=1,ai=2;
		while(n){
			if(n&1)	ans=ans*ai%MOD;
			ai=ai*ai%MOD;
			n>>=1;
		}
		printf("%lld\n",ans);
	}
	
	return 0;
}

 

相关标签: 算法