本篇內(nèi)容介紹了“Java高次冪取模+積性函數(shù)+逆元的方法”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

成都創(chuàng)新互聯(lián)公司是一家集網(wǎng)站建設(shè),定襄企業(yè)網(wǎng)站建設(shè),定襄品牌網(wǎng)站建設(shè),網(wǎng)站定制,定襄網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷,網(wǎng)絡(luò)優(yōu)化,定襄網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

題目意思：2004^x的所有正因數(shù)的和(S)對(duì)29求余；輸出結(jié)果；

原題鏈接

題目解析：解析參照來源：點(diǎn)擊打開鏈接

因子和

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.

這在數(shù)論中叫積性函數(shù)，當(dāng)gcd(a,b)=1時(shí)s(a*b)=s(a)*s(b);

如果p是素?cái)?shù)

s(p^n)=1+p+p^2+...+p^n=(p^(n+1)-1) /(p-1) (1)

例 hdu1452 Happy2004

計(jì)算 因子和 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)//根據(jù) （1）

b=s(3^X)= (3^(X+1)-1)/2//根據(jù) （1）

c=s(22^X)= (22^(X+1)-1)/21//根據(jù) （1）

%運(yùn)算法則
1. (a*b) %p= ( a%p) *(b%p)

%運(yùn)算法則
2. (a/b) %p= ( a *b^(-1)%p)

b^(-1)是
b的逆元素 （%p）

2的逆元素是15 （)） ，因?yàn)?*15=30 % 29=1 % 29

21的逆元素是18 （)） ，因?yàn)?1*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.積性函數(shù)：在數(shù)論中的積性函數(shù)：對(duì)于正整數(shù)n的一個(gè)算術(shù)函數(shù)
f(n)，若f(1)=1，且當(dāng)a,b互質(zhì)時(shí)f(ab)=f(a)f(b)，在數(shù)論上就稱它為積性函數(shù)。若
                                                       對(duì)于某積性函數(shù) f(n) ，就算a, b不互質(zhì)，也有f(ab)=f(a)f(b)，則稱它為完全積性的。若將n表示成質(zhì)因子分解式;
                    3.求逆元：
                           
在計(jì)算(a/b)%Mod時(shí)，往往需要先計(jì)算b%Mod的逆元p（b有逆元的條件是gcd(b,Mod)==1，顯然素?cái)?shù)肯定有逆元），然后由(a*p)%Mod      
  得結(jié)果c。這
 里b的逆元p滿足(b*p)%Mod=1。先來簡(jiǎn)單證明一下：
   (a/b)%Mod=c;    (b*p)%Mod=1;    ==》   (a/b)*(b*p) %Mod=c;    ==》    (a*p)%Mod=c;

從上面可以看出結(jié)論的正確性，當(dāng)然這里b需要是a的因子。接下來就需要知道根據(jù)b和Mod，我們?cè)趺从?jì)算逆元p了。擴(kuò)展歐幾里德算法，大家應(yīng)該都知道，就是已知a、b，求一組解(x,y)使得a*x+b*y=1。這里求得的x即為a%b的逆元，y為b%a的逆元（想想為什么？把方程兩邊都模上b或a看看）。

下面解釋原因：

模m乘法逆元

定義：對(duì)于整數(shù)a，m，如果存在整數(shù)b，滿足ab ≡ 1(mod m)，則說，b是a的模m乘法逆元。

定理：a存在模m的乘法逆元的充要條件是gcd(a,m) = 1

充分性：

因?yàn)?/p>

gcd(a,m) = 1

根據(jù)歐拉定理，有

a^φ(m) ≡ 1(mod m)

因此

a * a^(φ(m)-1) mod m = 1

所以存在a的模m乘法逆元，即a^(φ(m)-1)

必要性：

假設(shè)存在a模m的乘法逆元為b，則

ab ≡ 1 (mod m)

所以

ab = km +1

所以

1 = ab - km

由歐幾里得定理，有

gcd(a,m) = 1

由定理知：

對(duì)于ax + by = 1，可以看出x是a模b的乘法逆元，y是b模a的乘法逆元。

反過來，要計(jì)算a模b的乘法逆元，就相當(dāng)于求ax + by = 1的x的最小正整數(shù)解，從而化為線性不定方程解決。

具體參考：http://blog.csdn.net/synapse7/article/details/9901195調(diào)用ExtGcd（b,Mod,x,y)，x即為b%Mod的逆元p。 
  求b%Mod的逆元p還有另外一種方法，即p=b^(Mod-2)%Mod，因?yàn)閎^(Mod-1)%Mod=1(這里需要Mod為素?cái)?shù))。錯(cuò)誤分析：1:if(y&1)ans*=x%29;//誤把試中ans=x*x%292.數(shù)據(jù)類型要用__int64,

代碼實(shí)現(xiàn)：

#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是奇數(shù)情況的處理；
        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高次冪取模+積性函數(shù)+逆元的方法”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！

分享標(biāo)題：Java高次冪取模+積性函數(shù)+逆元的方法-創(chuàng)新互聯(lián)
文章分享：http://www.rwnh.cn/article24/cepgce.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站導(dǎo)航、微信小程序、移動(dòng)網(wǎng)站建設(shè)、搜索引擎優(yōu)化、定制開發(fā)、網(wǎng)站內(nèi)鏈

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)