ACM-ICPC 2018 焦作赛区网络预赛-G-Give Candies
程序员文章站
2022-03-04 21:07:22
...
地址: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;
}
下一篇: 安装Docker Compose
推荐阅读
-
ACM-ICPC 2018 徐州赛区网络预赛 H - Ryuji doesn't want to study
-
ACM-ICPC 2018 徐州赛区网络预赛 H. Ryuji doesn't want to study(线段树区间求和)
-
ACM-ICPC 2018 徐州赛区网络预赛 H. Ryuji doesn't want to study—— 树状数组
-
ACM-ICPC 2018 徐州赛区网络预赛 H Ryuji doesn't want to study(线段树 两种做法)
-
【ACM-ICPC 2018 徐州赛区网络预赛】H题 Features Track ---- 树状数组
-
ACM-ICPC 2018 徐州赛区网络预赛 G. Trace (线段树维护)
-
ACM-ICPC 2018 徐州赛区网络预赛 Trace
-
ACM-ICPC 2018 沈阳赛区网络预赛 F题 Fantastic Graph
-
ACM-ICPC 2018 沈阳赛区网络预赛-Made In Heaven-K短路
-
ACM-ICPC 2018 沈阳赛区网络预赛 - K Supreme Number - 推理