题目链接：
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
由于有分数求模，取逆元，还需用快速幂求幂值
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll pow(ll a, ll b, ll m)
{
ll ans = ;
while(b)
{
if(b & )ans = ans * a % m;
a *= a;
a %= m;
b /= ;
}
return ans;
}
ll extgcd(ll a, ll b, ll& x, ll& y)
//求解ax+by=gcd(a, b)
//返回值为gcd(a, b)
{
ll d = a;
if(b)
{
d = extgcd(b, a % b, y, x);
y -= (a / b) * x;
}
else x = , y = ;
return d;
}
ll mod_inverse(ll a, ll m)
//求解a关于模上m的逆元
//返回-1表示逆元不存在
{
ll x, y;
ll d = extgcd(a, m, x, y);
return d == ? (m + x % m) % m : -;
}
int main()
{
ll x;
while(cin >> x && x)
{
ll m = ;
ll a = pow(, * x + , m) - ;
ll b = pow(, x + , m) - ;
ll c = pow(, x + , m) - ;
ll ans = a * b * c * mod_inverse(, m) * mod_inverse(, m);
ans %= m;
cout<<ans<<endl;
}
return ;
}