PHP乘法逆元问题怎么解决

晶晶 • 04/08 21:59 • 开发 • 阅读 42

这篇文章主要讲解了“PHP乘法逆元问题怎么解决”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“PHP乘法逆元问题怎么解决”吧！Recommend

lcy

设S(x)表示x的因子和。则题目求为:S(2004^X)mod 29
因子和S是积性免费云主机域名函数,即满足性质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 是素数则 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的最小整数,这里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 c390MS感谢各位的阅读，以上就是“PHP乘法逆元问题怎么解决”的内容了，经过本文的学习后，相信大家对PHP乘法逆元问题怎么解决这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是百云主机，小编将为大家推送更多相关知识点的文章，欢迎关注！

相关推荐: python操作XML格式文件的常见方法实例分析

这篇文章主要介绍了python操作XML格式文件的常见方法实例分析的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇python操作XML格式文件的常见方法实例分析文章都会有所收获，下面我们一起来看看吧。可扩展标记语言，是一种简单的数…