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

Sample Output

Hint

1. For N = 2, S(1) = S(2) = 1. 2. The input file consists of multiple test cases.

Source

2013 Multi-University Training Contest 10

模型最终转换为求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))即为答案。

 1 //2017-08-04
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 #define ll long long
 7 
 8 using namespace std;
 9 
10 const int N = 100010;
11 const int MOD = 1000000007;
12 char str[N];
13 
14 ll quick_pow(ll a, ll n){//快速幂
15     ll ans = 1;
16     while(n){
17         if(n&1)ans = ans*a%MOD;
18         a = a*a%MOD;
19         n>>=1;
20     }
21     return ans;
22 }
23 
24 int main()
25 {
26     while(scanf("%s", str)!=EOF){
27         ll num = 0;
28         for(int i = 0; i < strlen(str); i++){//欧拉降幂
29             num *= 10;
30             num += str[i]-‘0‘;
31             num %= (MOD-1);
32         }
33         num -= 1;
34         printf("%lld\n", quick_pow(2, num));
35     }
36 
37     return 0;
38 }

HDU4704(SummerTrainingDay04-A 欧拉降幂公式)

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > HDU4704(SummerTrainingDay04-A 欧拉降幂公式)