本篇內容介紹了“Java高次冪取模+積性函數+逆元的方法”的有關知識,在實際案例的操作過程中,不少人都會遇到這樣的困境,接下來就讓小編帶領大家學習一下如何處理這些情況吧!希望大家仔細閱讀,能夠學有所成!
成都創(chuàng)新互聯公司是一家集網站建設,定襄企業(yè)網站建設,定襄品牌網站建設,網站定制,定襄網站建設報價,網絡營銷,網絡優(yōu)化,定襄網站推廣為一體的創(chuàng)新建站企業(yè),幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強企業(yè)競爭力。可充分滿足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯網需求。同時我們時刻保持專業(yè)、時尚、前沿,時刻以成就客戶成長自我,堅持不斷學習、思考、沉淀、凈化自己,讓我們?yōu)楦嗟钠髽I(yè)打造出實用型網站。題目意思: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即為a%b的逆元,y為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高次冪取模+積性函數+逆元的方法”的內容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關的知識可以關注創(chuàng)新互聯網站,小編將為大家輸出更多高質量的實用文章!
分享標題:Java高次冪取模+積性函數+逆元的方法-創(chuàng)新互聯
文章分享:http://m.newbst.com/article24/cepgce.html
成都網站建設公司_創(chuàng)新互聯,為您提供網站導航、微信小程序、移動網站建設、搜索引擎優(yōu)化、定制開發(fā)、網站內鏈
聲明:本網站發(fā)布的內容(圖片、視頻和文字)以用戶投稿、用戶轉載內容為主,如果涉及侵權請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網站立場,如需處理請聯系客服。電話:028-86922220;郵箱:631063699@qq.com。內容未經允許不得轉載,或轉載時需注明來源: 創(chuàng)新互聯