HDU 1452 Happy 2004 数论-白红宇

HDU 1452 Happy 2004 数论

阅读量：6050 次

发布时间：2019-06-20

本文共 1532 字，大约阅读时间需要 5 分钟。

　　题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1452

　　题目描述：让你求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 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #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

　　思考：通过本题自己对逆元的理解也深了一些，之前一直模棱两可的.......还有这种题都是有套路的，题做多了就好了

a*b*c-a*c-b*c+c-a*b+a+b

转载于:https://www.cnblogs.com/FriskyPuppy/p/7447741.html

你可能感兴趣的文章