Sum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 3245 Accepted Submission(s): 1332
Problem Description
Sample Input
2
Sample Output
2
Hint
1. For N = 2, S(1) = S(2) = 1.
2. The input file consists of multiple test cases.
Source
模型最终转换为求2^(b-1) mod (1e9+7),根据费马小定理可得1e9+7的欧拉函数为1e9+6。根据欧拉降幂公式a^b = a^(b%phi(MOD)+phi(MOD)) mod MOD,用快速幂算出a^(b%phi(MOD)+phi(MOD))即为答案。
//2017-08-04
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long using namespace std; const int N = ;
const int MOD = ;
char str[N]; ll quick_pow(ll a, ll n){//快速幂
ll ans = ;
while(n){
if(n&)ans = ans*a%MOD;
a = a*a%MOD;
n>>=;
}
return ans;
} int main()
{
while(scanf("%s", str)!=EOF){
ll num = ;
for(int i = ; i < strlen(str); i++){//欧拉降幂
num *= ;
num += str[i]-'';
num %= (MOD-);
}
num -= ;
printf("%lld\n", quick_pow(, num));
} return ;
}