题目链接
题解
题目大意:
求
[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
",(a-1)*(b-1)*15*(c-1)*18%mod);
}
return 0;
}