HDU 1452 Happy 2004 数论

古人学问无遗力，少壮工夫老始成。这篇文章主要讲述HDU 1452 Happy 2004 数论相关的知识，希望能为你提供帮助。
题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1452
【HDU 1452 Happy 2004 数论】题目描述：让你求2004^x的所有因数之和，模29
解题思路：先将2014质因数分解， 2^2 * 3 * 167，所以所有因数的个数就是(2x+1)*(x+1)*(x+1) ，我们列出公式，相当于一个空间直角坐标系，我们先将x, y平面上的点相加，再加z轴上的，最后得出公式
ans = (3^(x+1)-1) * (167^(x+1)-1)*(2^(2*x+1)-1)/332 即可，注意逆元
代码：

文章图片

#include < iostream> #include < cstdio> #include < string> #include < vector> #include < cstring> #include < iterator> #include < cmath> #include < algorithm> #include < stack> #include < deque> #include < map> #define lson l, m, rt< < 1 #define rson m+1, r, rt< < 1|1 #define mem0(a) memset(a,0,sizeof(a)) #define sca(x) scanf("%d",& x) #define de printf("=======\n") typedef long long ll; using namespace std; const int mod = 29; ll q_power( ll a, ll b ) { ll ret = 1; while( b ) { if( b & 1 ) ret = ret * a % mod; b > > = 1; a = a * a % mod; } return ret % mod; } ll exgcd(ll a, ll b, ll & x, ll & y) { if(b == 0) { x = 1; y = 0; return a; } else { ll ret = exgcd(b, a%b, x, y); ll tmp = x; x = y; y = tmp - a / b * y; return ret; } } ll inv(ll a) { ll x, y; exgcd(a, mod, x, y); return (x % mod + mod) % mod; } int main() { ll x; while( scanf( "%lld", & x ) == 1 & & x ) { ll ans; ll a = q_power(3, x+1); ll b = q_power(167, x+1); ll c = q_power(2, 2*x+1); ans = (a*b*c-a*c-b*c+c-a*b+a+b-1) * inv(332) % mod; printf( "%lld\n", ans ); } return 0; }

View Code思考：通过本题自己对逆元的理解也深了一些，之前一直模棱两可的.......还有这种题都是有套路的，题做多了就好了
p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 14.0px Menlo; color: #ffffff } span.s1 { }a*b*c-a*c-b*c+c-a*b+a+b
p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 14.0px Menlo; color: #ffffff } span.s1 { }a*b*c-a*c-b*c+c-a*b+a+b
p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 14.0px Menlo; color: #ffffff } span.s1 { }a*b*c-a*c-b*c+c-a*b+a+b