題目意思：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));
b=(powi(3,x 1,29)-1)*15 );
c=(powi(22,x 1,29) -1)*18 );
ans=（a*b）% 29*c % 29;
資料拓展： 1.
高次冪快速取模連結
2.積性函數：數論中的積性函數：對於正整數##n
#n
a###,bb)f(互質時f(aab
)=f()，在數論上就稱它為積性函數。若裡b的逆元p滿足(b*p)%Mod=1。先來簡單證明：完全積性的。若將得結果c。這n逆元p（b有逆元的條件是gcd(b,Mod)==1，顯然素數肯定有逆元），然後由(a*p)%Mod表示成質因子分解式;
3.求逆：(a/b)%Mod=c; (b*p)%Mod=1; ==》 (a/b)*(b*p) %Mod=c; ====== (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的最小正整數解，從而化為線性不定方程式解決。求b%Mod的逆元p還有另一種方法，即p=b^(Mod-2)%Mod，因為b^(Mod-1)%Mod=1(這裡需要Mod為質數)。錯誤分析：1:if(y&1)ans*=x);//誤把試中ans=x*x)2.資料型別要用__int64,程式碼實作：
具體參考：http://blog.csdn.net/synapse7/article/details/9901195呼叫ExtGcd（b,Mod,x,y)，x即為b%Mod的逆元p。
#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中文網其他相關文章！
