锐客网

  1. 首页 > 睿知 > it技术 > >

Happy 2004 hdu1452

IT知识happy

提兵百万西湖上，立马吴山第一峰！这篇文章主要讲述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; }











    推荐阅读


    上一篇：com.android.support冲突的解决办法

    下一篇：给 Android 开发人员的 RxJava 具体解释