HDU1452 Happy 2004【因数之和】

浏览数：40 / 时间：2015年06月11日

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1452

题目大意：

对于一个正整数X，令S是2004^X的所有约数和。现在计算S%29的结果。

思路：

先将2004分解素因子，2004 = 2^(2*X) * 3^X * 167^X，所以

S = (2^(2*X+1) - 1)/(2-1) * (3^(X+1) - 1)/(3-1) * (167^(X+1) - 1)/(167-1)。

S = (2^(2*X+1) - 1) * (3^(X+1) - 1)/2 * (167^(X+1) - 1)/166

令

a = 2^(2*X+1) - 1，

b = (3^(X+1) - 1)/2

c = (167^(X+1) - 1)/166

根据%运算法则：

1. (a*b) %p= ( a%p) *(b%p)

2. (a/b) %p= ( a *b^(-1)%p) b^(-1)为a模p的逆元。

求得：167%29 = 22，166%29 = 21，2模29的逆元为15，21模29的逆元为18，则：

a = (2^(2*X+1) - 1) % 29

b = (3^(X+1) - 1) * 15 % 29

c = (22^(X+1) - 1) * 18 % 29

最终结果为：ans = a*b%29*c%29

AC代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

int QuickPower(int a,int b,int mo)
{
    int ret = 1;
    while(b > 0)
    {
        if(b&1)
            ret = ret * a % mo;
        a = a * a % mo;
        b >>= 1;
    }
    return ret;
}

int main()
{
    int N;
    while(~scanf("%d",&N) && N)
    {
        N %= 28;
        int a,b,c;
        a = (QuickPower(2,2*N+1,29)-1)%29;
        b = (QuickPower(3,N+1,29)-1)*15%29;
        c = (QuickPower(167,N+1,29)-1)*18%29;
        int ans = a*b%29*c%29;
        printf("%d\n",ans);
    }

    return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

HDU1452 Happy 2004【因数之和】