這篇文章主要講解了“PHP乘法逆元問題怎么解決”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“PHP乘法逆元問題怎么解決”吧！

10余年的黟縣網(wǎng)站建設(shè)經(jīng)驗，針對設(shè)計、前端、開發(fā)、售后、文案、推廣等六對一服務(wù)，響應(yīng)快，48小時及時工作處理。成都全網(wǎng)營銷推廣的優(yōu)勢是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動調(diào)整黟縣建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計，從而大程度地提升瀏覽體驗。成都創(chuàng)新互聯(lián)從事“黟縣網(wǎng)站設(shè)計”,“黟縣網(wǎng)站推廣”以來，每個客戶項目都認(rèn)真落實執(zhí)行。

Recommend lcy  

設(shè)S(x)表示x的因子和。則題目求為:S(2004^X)mod 29
因子和S是積性函數(shù),即滿足性質(zhì)1。

性質(zhì)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)

性質(zhì)2 ：如果 p 是素數(shù) 則 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

性質(zhì)3 ：(a*b)/c %M= a%M * b%M * inv(c)
其中inv(c)即滿足 (c*inv(c))%M=1的最小整數(shù),這里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

快速冪取模就是在O(logn)內(nèi)求出a^n mod b的值。算法的原理是ab mod c=(a mod c)(b mod c)mod c 390MS

#include<iostream>
using namespace std;
const int pow[][3]={{2,5,32},{3,4,81},{22,2,484}};
//2^5>29,3^4>29,22^2>29,用于求(b^i)%29
int PowMod29(int x,int index)   //快速模冪
{
	int ans=1;
	while(index>=pow[x][1]) //當(dāng)指數(shù)大于這個值將會超過29
	{
		ans=(ans*pow[x][2])%29;  //所以要模29.并且要乘上前面的值！
		index-=pow[x][1];
	}
	while(index--) ans=(ans*pow[x][0])%29;//把剩余的不超過29的乘上！再記得模上29（因為有可能超過29）
	return ans;
}
int main()
{
	int X,part2,part3,part167;
	while(cin>>X&&X!=0)
	{
		part2=PowMod29(0,2*X+1);
		part3=PowMod29(1,X+1);
		part167=PowMod29(2,X+1);
		cout<<((part2-1)*(part3-1)*15*(part167-1)*18)%29<<endl;//再模29，因為有超過29的可能.
	}
	return 0;
}

感謝各位的閱讀，以上就是“PHP乘法逆元問題怎么解決”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對PHP乘法逆元問題怎么解決這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！

網(wǎng)頁題目：PHP乘法逆元問題怎么解決
網(wǎng)頁地址：http://chinadenli.net/article16/ipscdg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、ChatGPT、網(wǎng)站改版、動態(tài)網(wǎng)站、網(wǎng)站排名、軟件開發(fā)

廣告

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