题目意思：2004^x的所有正因数的和(S)对29求余；输出结果；
原题链接
题目解析：解析参照来源：点击打开链接
因子和
6的因子是1,2,3,6; 6的因子和是s(6)=1+2+3+6=12;
20的因子是1,2,4,5,10,20; 20的因子和是s(20)=1+2+4+5+10+20=42;
2的因子是1,2; 2的因子和是s(2)=1+2=3;
3的因子是1,3; 3的因子和是s(3)=1+3=4;
4的因子和是
s(4)=1+2+4=7;
5的因子和是
s(5)=1+5=6;
s(6)=s(2)*s(3)=3*4=12;
s(20)=s(4)*s(5)=7*6=42;
这是巧合吗？
再看 s(50)=1+2+5+10+25+50=93=3*31=s(2)*s(25),s(25)=1+5+25=31.
这在数论中叫积性函数，当gcd(a,b)=1时s(a*b)=s(a)*s(b);
如果p是素数
s(p^n)=1+p+p^2+...+p^n=(p^(n+1)-1) /(p-1) (1)
例 hdu1452 Happy2004
计算 因子和 s(2004^X) mod 29,
2004=2^2 *3 *167
s(2004^X) ) = (s(2^2X))) *(s(3^X))) * (s(167^X)))
167)=22;
s(2004^X) ) = (s(2^2X))) *(s(3^X))) * (s(22^X)))
a=s(2^2X)=(2^(2X+1)-1)//根据 （1）
b=s(3^X)= (3^(X+1)-1)/2//根据 （1）
c=s(22^X)= (22^(X+1)-1)/21//根据 （1）
%运算法则
1. (a*b) %p= ( a%p) *(b%p)
%运算法则
2. (a/b) %p= ( a *b^(-1)%p)
b^(-1)是
b的逆元素 （%p）
2的逆元素是15 （)） ，因为2*15=30 % 29=1 % 29
21的逆元素是18 （)） ，因为21*18=378% 29 =1 % 29
因此
a=（powi(2,2*x+1,29)-1）%29;
b=(powi(3,x+1,29)-1)*15 %29;
c=(powi(22,x+1,29)-1)*18 %29;
ans=（a*b）% 29*c % 29;
资料拓展： 1.
高次幂快速取模链接
2.积性函数：在数论中的积性函数：对于正整数n的一个算术函数
f(n)，若f(1)=1，且当a,b互质时f(ab)=f(a)f(b)，在数论上就称它为积性函数。若
对于某积性函数 f(n) ，就算a, b不互质，也有f(ab)=f(a)f(b)，则称它为完全积性的。若将n表示成质因子分解式;
3.求逆元：
在计算(a/b)%Mod时，往往需要先计算b%Mod的逆元p（b有逆元的条件是gcd(b,Mod)==1，显然素数肯定有逆元），然后由(a*p)%Mod
得结果c。这
里b的逆元p满足(b*p)%Mod=1。先来简单证明一下：
(a/b)%Mod=c; (b*p)%Mod=1; ==》 (a/b)*(b*p) %Mod=c; ==》 (a*p)%Mod=c;
从上面可以看出结论的正确性，当然这里b需要是a的因子。接下来就需要知道根据b和Mod，我们怎么计算逆元p了。大家都应该熟悉扩展欧几里德算法，它用于解决已知a、b时求一组解(x,y)，使得a*x+b*y=1。x和y分别是a对b取模的逆元和b对a取模的逆元，可通过模上b或a来验证。
下面解释原因：
模m乘法逆元
定义：对于整数a，m，如果存在整数b，满足ab ≡ 1(mod m)，则说，b是a的模m乘法逆元。
定理：a存在模m的乘法逆元的充要条件是gcd(a,m) = 1
充分性：
因为
gcd(a,m) = 1
根据欧拉定理，有
a^φ(m) ≡ 1(mod m)
因此
a * a^(φ(m)-1) mod m = 1
所以存在a的模m乘法逆元，即a^(φ(m)-1)
必要性：
假设存在a模m的乘法逆元为b，则
ab ≡ 1 (mod m)
所以
ab = km +1
所以
1 = ab - km
由欧几里得定理，有
gcd(a,m) = 1
由定理知：
对于ax + by = 1，可以看出x是a模b的乘法逆元，y是b模a的乘法逆元。
反过来，要计算a模b的乘法逆元，就相当于求ax + by = 1的x的最小正整数解，从而化为线性不定方程解决。
具体参考：http://blog.csdn.net/synapse7/article/details/9901195调用ExtGcd（b,Mod,x,y)，x即为b%Mod的逆元p。
求b%Mod的逆元p还有另外一种方法，即p=b^(Mod-2)%Mod，因为b^(Mod-1)%Mod=1(这里需要Mod为素数)。错误分析：1:if(y&1)ans*=x%29;//误把试中ans=x*x%292.数据类型要用__int64,代码实现：
#include<cstdio>
#include<cstdlib>
using namespace std;
typedef __int64 ll;
ll powmol(ll x,ll y)//高次幂取模的求x^ymod29
{
ll ans=1;
x=x%29;
while(y)
{
if(y&1)ans*=x%29;//y是奇数情况的处理；
x=x*x%29;
y>>=1;//
}
return ans;
}
int main()
{
ll x,a,b,c;
while(scanf("%I64d",&x),x)
{
a=(powmol(2,2*x+1)-1)%29;
b=(powmol(3,x+1)-1)*15%29;
c=(powmol(22,x+1)-1)*18%29;
printf("%I64d\n",(a*b)%29*c%29);
}
return 0;
}以上是Java高次幂取模+积性函数+逆元的方法的详细内容。更多信息请关注PHP中文网其他相关文章！
