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

目前創(chuàng)新互聯(lián)已為1000+的企業(yè)提供了網(wǎng)站建設、域名、雅安服務器托管、網(wǎng)站托管、服務器托管、企業(yè)網(wǎng)站設計、永靖網(wǎng)站維護等服務，公司將堅持客戶導向、應用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

Recommend lcy

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

性質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)

性質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

性質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)內求出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]) //當指數(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乘法逆元問題怎么解決”的內容了，經(jīng)過本文的學習后，相信大家對PHP乘法逆元問題怎么解決這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是創(chuàng)新互聯(lián)網(wǎng)站建設公司，，小編將為大家推送更多相關知識點的文章，歡迎關注！

當前名稱：PHP乘法逆元問題怎么解決-創(chuàng)新互聯(lián)
轉載注明：http://www.aaarwkj.com/article14/ddojge.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供用戶體驗、移動網(wǎng)站建設、網(wǎng)站維護、定制開發(fā)、關鍵詞優(yōu)化、網(wǎng)站排名

廣告

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