G - Happy 2004------(HDU 1452)

简介:

传送门

Happy 2004

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1346    Accepted Submission(s): 977


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的值;

解题思路:

首先根据算术基本定理(1),
若 n 的标准素因子分解表达式为 n = p1^e1 * p2^e2 * …… * pk^ek
设f(n) 为n 的所有因子之和,则有:
f(n) = (p1^(e1+1)-1)/(p1-1) * (p2^(e2+1)-1)/(p2-1) * ... * (pk^(ek+1)-1)/(pk-1)
因为2004 = 2^2 * 3 * 167,所以2004^x也肯定是2^(2*x) * 3^x * 167^x;
然后根据算术基本定理:
167 Mod 29 == 22 所以直接用22就行
((2^(2*x+1)-1)/(2-1) * (3^(x+1)-1)/(3-1) *  (22^(x+1)-1)/(22-1)) Mod 29 
设a = (2^(2*x+1)-1)/1;
设b = (3^(x+1)-1)/2 ;
设c = (22^(x+1)-1)/21);
我们只要分别求出 a Mod 29, b Mod 29, c Mod 29的值就行啦,因为他们带着除数所以 我们进行求解逆元,分别是
1Mod29的逆元 2Mod29的逆元 21Mod29的逆元,这个可以根据扩展欧几里得算法得到,求出之后,我们就进行快速幂 分别求出2^(2x+1)Mod 29 , 3^(x+1)Mod 29,  22^(x+1)Mod 29 的值,然后减一 与 前面所求的逆元进行相乘就ok了
最后输出的就是 a*b*c Mod 29,下面是详细代码:

#include <iostream>

using namespace std;
typedef long long LL;
LL quick_mod(LL a, LL b, LL m)
{
    LL ans = 1;
    while(b)
    {
        if(b & 1)
            ans = (ans*a)%m;
        b>>=1;
        a = (a*a)%m;
    }
    return ans;
}
void exgcd(LL a, LL b, LL &x, LL &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return;
    }
    LL x1, y1;
    exgcd(b, a%b, x1, y1);
    x = y1;
    y = x1 - (a/b)*y1;
}
int main()
{
    LL n, a, b, c, y, _a, _b, _c;
    while(cin>>n,n)
    {
        exgcd(1,29,_a,y);
        exgcd(2,29,_b,y);
        exgcd(21,29,_c,y);
        _a = (_a+29)%29;
        _b = (_b+29)%29;
        _c = (_c+29)%29;
        ///cout<<167%29<<endl;
        ///cout<<_a<<" "<<_b<<" "<<_c<<endl;
        a=(quick_mod(2,2*n+1,29)-1)*_a;
        b=(quick_mod(3,n+1,29)-1)*_b;
        c=(quick_mod(22,n+1,29)-1)*_c;
        cout<<(a*b*c%29)<<endl;
    }
    return 0;
}


目录
相关文章
|
6月前
|
Java
HDU-1896-Stones
HDU-1896-Stones
26 0
|
6月前
|
Java
HDU-4552-怪盗基德的挑战书
HDU-4552-怪盗基德的挑战书
35 0
|
12月前
|
Java 文件存储
hdu1128 Self Numbers
hdu1128 Self Numbers
34 0
|
算法 Java
HDU 2084 数塔
在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这样描述的: 有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少?
174 0
|
人工智能 Java
hdu 1712 ACboy needs your help
ACboy这学期有N门课程,他计划花最多M天去学习去学习这些课程,ACboy再第i天学习第j门课程的收益是不同的,求ACboy能获得的最大收益。
135 0
HDU 2669 Romantic
题意:找出最小的非负整数X,使之满足式子X*a + Y*b = 1。
108 0
|
C++ Java
HDU1880
题意就是根据咒语查功能,根据功能查看是否存在相应咒语,题意简单,不过是道不错的练习题。         下面的都MLE了,听说C++用G++提交才可以AC,否则也MLE;方法很多,不想做了……         方法一:我用Java的HashMap一直MLE,即便由value反查key减少映射数也一样MLE,听说C++的map可以AC。
1080 0