hdu-1452 Happy 2004---因子和+逆元

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1452

题目大意：

求2004^x次方的因子和mod29的值

解题思路：

首先2004 = 2 * 2 * 3 * 167

所以2004^x = 2^(2x) * 3 ^(x) * 167 ^ (x)

因子和为：

[ (2^(2x+1) - 1) / (2 - 1) ] * [(3 ^ (x+1) - 1) / (3 - 1)] * [(167 ^ (x+1) - 1) / (167 - 1)]

最终mod29

由于有分数求模，取逆元，还需用快速幂求幂值

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll pow(ll a, ll b, ll m)
 5 {
 6     ll ans = 1;
 7     while(b)
 8     {
 9         if(b & 1)ans = ans * a % m;
10         a *= a;
11         a %= m;
12         b /= 2;
13     }
14     return ans;
15 }
16 ll extgcd(ll a, ll b, ll& x, ll& y)
17 //求解ax+by=gcd(a, b)
18 //返回值为gcd(a, b)
19 {
20     ll d = a;
21     if(b)
22     {
23         d = extgcd(b, a % b, y, x);
24         y -= (a / b) * x;
25     }
26     else x = 1, y = 0;
27     return d;
28 }
29 ll mod_inverse(ll a, ll m)
30 //求解a关于模上m的逆元
31 //返回-1表示逆元不存在
32 {
33     ll x, y;
34     ll d = extgcd(a, m, x, y);
35     return d == 1 ? (m + x % m) % m : -1;
36 }
37 int main()
38 {
39     ll x;
40     while(cin >> x && x)
41     {
42         ll m = 29;
43         ll a = pow(2, 2 * x + 1, m) - 1;
44         ll b = pow(3, x + 1, m) - 1;
45         ll c = pow(167, x + 1, m) - 1;
46         ll ans = a * b * c * mod_inverse(2, m) * mod_inverse(166, m);
47         ans %= m;
48         cout<<ans<<endl;
49     }
50     return 0;
51 }