hdu 1425 Happy 2004

行是知之始,知是行之成。这篇文章主要讲述hdu 1425 Happy 2004相关的知识,希望能为你提供帮助。
题目链接
hdu 1425 Happy 2004
题解
【hdu 1425 Happy 2004】题目大意:

\[\sum_{d|2004^{x}}d\ mod\ 29\]
记为\(s(2004^x)\)
\(sum(2004^{x})= s(2^2X)) * s(3^X) * s(167^X)\)
$167?mod?29 = 22 $
\(s(2004^X) = s(2^{2X}) * s(3^{X})) * s(22^X)\)
此时底数变为了质数
如果p是素数
\(s(p^n)=1+p+p^2+...+p^n= (p^{n+1}-1) / (p-1) (1)\)
上面的式子带下来,写代码就好了
对于除法取mod需要求逆元
29为素数-> 快速幂
或者,打个表不就好了嘛233
代码

#include< cmath> #include< cstdio> #include< algorithm> inline int read() { int x=0,f=1; char c=getchar(); while(c< ' 0' ||c> ' 9' )c=getchar(); while(c< =' 9' & & c> =' 0' )x=x*10+c-' 0' ,c=getchar(); return x; } #define mod 29 int x,a,b,c; int pow(int a,int p) { int ret=1; for(; p; p> > =1,a=a*a%mod) { if(p& 1)ret=ret*a%mod; } return ret; } int main() { while(1) { x=read(); if(!x)break; a=pow(2,2*x+1); b=pow(3,x+1); c=pow(22,x+1); printf(" %d\n" ,(a-1)*(b-1)*15*(c-1)*18%mod); } return 0; }


    推荐阅读