行是知之始,知是行之成。这篇文章主要讲述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;
}
推荐阅读
- 智能家居 手机一键自配置APP
- 数据分区------《Designing Data-Intensive Applications》读书笔记9
- 课程四(Convolutional Neural Networks),第四 周(Special applications: Face recognition & Neural style tr
- Android Studio修改默认Activity继承AppCompatActivity(转)
- HTML5 唤起 APP
- Android.mk 宏
- Android.mk 计算怎么办()
- android开发游记(ItemTouchHelper 使用RecyclerView打造可拖拽的GridView)
- Android.mk函数