HDU 1452 Happy 2004 快乐2004

「爱情、让人受尽委屈。」 2022-07-29 10:58 139阅读 0赞

HDU 1452 Happy 2004 快乐2004 ：[http://acm.hdu.edu.cn/showproblem.php?pid=1452][http_acm.hdu.edu.cn_showproblem.php_pid_1452]

题面：

# Happy 2004 #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 1351 Accepted Submission(s): 982**

Problem Description

Consider a positive integer X,and let S be the sum of all positive integer divisors of 2004^X. Your job is to determine S modulo 29 (the rest of the division of S by 29).  
  
Take X = 1 for an example. The positive integer divisors of 2004^1 are 1, 2, 3, 4, 6, 12, 167, 334, 501, 668, 1002 and 2004. Therefore S = 4704 and S modulo 29 is equal to 6.

Input

The input consists of several test cases. Each test case contains a line with the integer X (1 <= X <= 10000000).  
  
A test case of X = 0 indicates the end of input, and should not be processed.

Output

For each test case, in a separate line, please output the result of S modulo 29.

Sample Input

1
    10000
    0

Sample Output

6
    10

题目大意：

求2004^x所有因子的和并对29求模之后的结果。

题目分析：

先对2004进行素因子分解，可以得到2004=2^2\*3\*167，则2004^x=2^(2x)\*3^x\*167^x； //素因子分解

由算数基本定理：Φ(n)为n的所有因子之和，则有：

![Center][]

由题意，可计算得：

![Center 1][]

根据上述公式，用快速幂求解即可；

其中用到的公式和定理如下：

(a/b)mod m=(b^-1\*a)mod m // b^-1指的是b的逆元，要用扩展欧几里得求解，t徒手求解过程如下：

332\*x+29\*y=1

332=11\*29+13

29=2\*13+3

13=4\*3+1

3=3\*1

即gcd(332,29)=1

1=13-4\*3

=13-4\*(29-2\*13)

=-4\*29+9\*13

=-4\*29+9\*(332-11\*29)

=9\*332-103\*29

则x=9;

(a+b)mod m=(a mod m+b mod m)mod m

(a^b)mod m=(a mod m)^b mod m

(a\*b)mod m=((a mod m)\*(b mod m))mod m

附快速幂代码：

long long quick_mod(long long a,long long b,long long M)
    {
        long long ans=1;
        while(b)
        {
            if(b&1)
            {
                ans=(ans*a)%M;
                b--;
            }
            b/=2;
            a=a*a%M;
        }
        return ans;
    }

代码实现：

#include <stdio.h>
    #include <string.h>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <stack>
    #include <set>
    #include <map>
    #include <string>
    #include <math.h>
    #include <stdlib.h>
    #include <time.h>
    using namespace std;
    typedef long long ll;
    const int INF = 0x3f3f3f3f;
    const double eps = 1e-4;
    const int M=29;
    
    long long quick_mod(long long a,long long b)
    {
        long long ans=1;
        while(b)
        {
            if(b&1)
            {
                ans=(ans*a)%M;
                b--;
            }
            b/=2;
            a=a*a%M;
        }
        return ans;
    }
    
    int main()
    {
        int x;
        while(scanf("%d",&x)!=EOF)
        {
            if(x==0)
            break;
            int sum;
            int a=(quick_mod(2,2*x+1)-1)%29;
            int b=(quick_mod(3,x+1)-1)%29;
            int c=(quick_mod(22,x+1)-1)%29;
            sum=(9*a*b*c)%29;
            printf("%d\n",sum);
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1452]: http://http://acm.hdu.edu.cn/showproblem.php?pid=1452
[Center]: /images/20220728/774c3232845642afa51593d048f7d33c.png
[Center 1]: /images/20220728/dd06300e4ad349b9840f246f69770708.png