提兵百万西湖上，立马吴山第一峰！这篇文章主要讲述Happy 2004 hdu1452相关的知识，希望能为你提供帮助。
Time Limit: 2000/1000 MS (java/Others)
Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2021
Accepted Submission(s): 1474
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.
【Happy 2004 hdu1452】
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 Input1
10000
0
Sample Output6
10
数论题，推理挺麻烦的：
题目的大意是说求2004^n的全部因子之和。
根据唯一分解定理2004=(2^2)*3*167,则2004^n=(2^2n)*(3^n)*(167^n);
又有结论：一个因数的因子和是一个积性函数。设f(x)为x的因子和，则f(ab)=f(a)*f(b);
则f(2004^n)=f(2^2n)*f(3^n)*f(167^n).
继续上结论：如果一个数是素数，那么f(a^n)=1+a+a^2+a^3+.......a^n=(a^(n+1)-1)/(a-1);
考虑到 167%29=22；
则f(2004^n)=(2^(2n+1)-1) * (3^(n+1)-1)/2 * (22^(n+1)-1)/21;
接着上逆元： (a*b/c)%mod=a%mod*b%mod*inv(c);
其中inv(c)表示(c*inv(c))%mod=1的最小整数. mod=29，则inv(1)=1;
inv(2)=15;
inv(21)=18;
则原式=(2^(2n+1)-1)*(3^(n+1)-1)%mod*inv(2)*
(22^(n+1)-1)*inv(21)
15*18%29=9---------------则原式(2^(2n+1)-1) * (3^(n+1)-1)* (22^(n+1)-1)*9%29;
#include < iostream> #include < bits/stdc++.h> using namespace std; typedef long long ll; int ans=0; const int mod=29; ll quick_mod(ll k,ll n) { ll res=1; while(n> 0) { if(n& 1) { res=(res*k)%mod; } k=k*k%mod; n> > =1; } res--; if(res< 0) res+=29; return res; } int main() { ll n; while(~scanf("%lld",& n)& & n) { ans=quick_mod(2,2*n+1)*quick_mod(3,n+1)*quick_mod(22,n+1)*9%mod; printf("%d\n",ans); } return 0; }
推荐阅读
- 给 Android 开发人员的 RxJava 具体解释
- com.android.support冲突的解决办法
- Elasticsearch 全文搜索和keyword search字段的mapping定义
- springmvc注解@RequestMapping
- Android P专区免费开放 -- 同样的Android，不同的体验
- Applets
- Android ListView多选模式
- 实例演示Android安全须知
- applet