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

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

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 是素?cái)?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
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ù)大于這個(gè)值將會(huì)超過29
	{
		ans=(ans*pow[x][2])%29;  //所以要模29.并且要乘上前面的值！
		index-=pow[x][1];
	}
	while(index--) ans=(ans*pow[x][0])%29;//把剩余的不超過29的乘上！再記得模上29（因?yàn)橛锌赡艹^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<

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

名稱欄目：PHP乘法逆元問題怎么解決-創(chuàng)新互聯(lián)
文章分享：http://weahome.cn/article/ddojge.html