Question

杭电acm1452题，用c语言怎么解决？请高手指点了，求代码、思想、详解。

Answer 1

题目大意：给你一个x，求2004的x次方所有因子对29取余
解题思路：属于数学题，主要应用初等数论中的最大公因子的性质、费马小定理（如果不清楚的话建议学习一下，acm中数学题应用的数学公式）
设S(x)表示x的因子和。则题目求为:S(2004^X)mod 29
因子和S是积性函数,即满足性质1。
性质1 ：如果 gcd(a,b)=1 则 S(a*b)= S(a)*S(b)
2004^X=4^X * 3^X *167^X
S(2004^X)=S(2^(2X)) * S(3^X) * S(167^X)
性质2 ：如果 p 是素数 则 S(p^X)=1+p+p^2+...+p^X = (p^(X+1)-1)/(p-1)
因此：S(2004^X)=(2^(2X+1)-1) * (3^(X+1)-1)/2 * (167^(X+1)-1)/166
167%29 == 22
S(2004^X)=(2^(2X+1)-1) * (3^(X+1)-1)/2 * (22^(X+1)-1)/21
性质3 ：(a*b)/c %M= a%M * b%M * inv(c)
其中inv(c)即满足 (c*inv(c))%M=1的最小整数,这里M=29
则inv(1)=1，inv(2)=15，inv(22)=15
有上得：
S(2004^X)=(2^(2X+1)-1) * (3^(X+1)-1)/2 * (22^(X+1)-1)/21
=(2^(2X+1)-1) * (3^(X+1)-1)*15 * (22^(X+1)-1)*18

源程序参考：（不唯一）
#include <stdio.h>
int a2[28]={1,2,4,8,16,3,6,12,24,19,9,18,7,14,28,27,25,21,13,26,23,17,5,10,20,11,22,15};
int a3[28]={1,3,9,27,23,11,4,12,7,21,5,15,16,19,28,26,20,2,6,18,25,17,22,8,24,14,13,10};
int a167[28]={1,22,20,5,23,13,25,28,7,9,24,6,16,4,1,22,20,5,23,13,25,28,7,9,24,6,16,4};
int main()
{
for(int i=1;i<29;i++)
{
a2[i]=(a2[i]+a2[i-1])%29;
a3[i]=(a3[i]+a3[i-1])%29;
a167[i]=(a167[i]+a167[i-1])%29;
}
int n;
while(scanf("%d",&n),n)
{
int b2=a2[n*2% 28]+((n*2 / 28))%29*a2[28]%29;
int b3= a3[n % 28]+((n / 28))%29*a3[28]%29;
int b167=a167[n % 28]+((n / 28))%29*a167[28]%29;
printf("%d\n",b2*b3*b167%29);
}
return 0;
}

Answer 2

那个讨论区不是也有吗？我看了一眼代码，也不怎么长，应该有点规律的。

Answer 3

去CSDN发贴吧