ACM-ICPC 2018 焦作赛区网络预赛 - G Give Candies - 规律+欧拉降幂
程序员文章站
2022-03-12 15:28:16
...
思路:
找规律可以知道是2^(n-1)
n的范围很大,所以用欧拉降幂公式降幂:
欧拉φ函数:在数论中,对正整数n,欧拉函数是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名,它又称为φ函数、欧拉商数等。φ(1)=1
m=1e9+7是个质数,所以φ(1e9+7)=1e9+6
给质数降幂后就愉快地用快速幂求解好了~
代码如下:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<string>
#include<cstring>
using namespace std;
#define ll long long
const int mod=1e9+7,md=1e9+6;
ll mod_pow(ll a,ll b){
ll res=1;
while(b){
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int main(){
int t;
scanf("%d",&t);
string s;
while(t--){
cin>>s;
ll mi=0;
for(int i=0;i<s.length();i++){
mi=(mi*10+s[i]-'0')%md;
}
mi=(mi-1+md)%md;
printf("%lld\n",mod_pow(2,mi));
}
}