本篇内容介绍了“Java高次幂取模+积性函数+逆元的方法”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!题目意思:2004^x的所有正因数的和(S)对29求余;输出结果;原题链接题目解析:解析参照来源:点击打开链接因子和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.这在数论中叫积性函数,当gcd(a,b)=1时s(a*b)=s(a)*s(b);如果p是素数s(p^n)=1+p+p^2+…+p^n=(p^(n+1)-1) /(p-1) (1)例 hdu1452 Happy2004计算 因子和 s(2004^X) mod 29,2004=2^2 *3 *167s(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)//根据 (1)b=s(3^X)= (3^(X+1)-1)/2//根据 (1)c=s(22^X)= (22^(X+1)-1)/21//根据 (1)%运算法则
1. (a*b) %p= ( a%p) *(b%p)%运算法则
2. (a/b) %p= ( a *b^(-1)%p)b^(-1)是
b的逆元素 (%p)2的逆元素是15 ()) ,因为2*15=30 % 29=1 % 2921的逆元素是18 ()) ,因为21*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.积性函数:在数论中的积性函数:对于正整数n的一个算术函数
f(n),若f(1)=1,且当a,b互质时f(ab)=f(a)f(b),在数论上就称它为积性函数。若
对于某积性函数 f(n) ,就算a, b不互质,也有f(ab)=f(a)f(b),则称它为完全积性的。若将n表示成质因子分解式;
3.求逆元:
在计算(a/b)%Mod时,往往需要先计算b%Mod的逆元p(b有逆元的条件是gcd(b,Mod)==1,显然素数肯定有逆元),然后由(a*p)%Mod
得结果c。这
里b的逆元p满足(b*p)%Mod=1。先来简单证明一下:
(a/b)%Mod=c; (b*p)%Mod=1; ==》 (a/b)*(b*p) %Mod=c; ==》 (a*p)%Mod=c;
从上面可以看出结论的正确性,当然这里b需要是a的因子。接下来就需要知道根据b和Mod,我们怎么计算逆元p了。扩展欧几里德算法,大家应该都知道,就是已知a、b,求一组解(x,y)使得a*x+b*y=1。这里求得的x即为a%b的逆元,y为b%a的逆元(想想为什么?把方程两边都模上b或a看看)。下面解释原因:模m乘法逆元定义:对于整数a,m,如果存在整数b,满足ab≡1(mod m),则说,b是a的模m乘法逆元。定理:a存在模m的乘法逆元的充要条件是gcd(a,m) = 1充分性:因为gcd(a,m) = 1根据欧拉定理,有a^(m) ≡ 1(mod m)因此a * a^((m)-1) mod m = 1所以存在a的模m乘法逆元,即a^((m)-1)必要性:假设存在a模m的乘法逆元为b,则ab ≡ 1 (mod m)所以ab = km +1所以1 = ab – km由欧几里得定理,有gcd(a,m) = 1由定理知:对于ax + by = 1,可以看出x是a模b的乘法逆元,y是b模a的乘法逆元。反过来,要计算a模b的乘法逆元,就相当于求ax + by = 1的x的最小正整数解,从而化为线性不定方程解决。具体参考:http://blog.csdn.net/synapse7/article/details/9901195调用ExtGcd(b,Mod,x,y),x即为b%Mod的逆元p。
求b%Mod的逆元p还有另外一种方法,即p=b^(Mod-2)%Mod,因为b^(Mod-1)%Mod=1(这里需要Mod为素数)。错误分析:1:if(y&1)ans*=x%29;//误把试中ans=x*x%292.数据类型要用__int64,代码实现:“Java高次幂取模+积性函数+逆元的方法”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注百云主机网站,小编将为大家输出更多高质量的实用文章!
这篇文章主要介绍了Node.js环境提供了哪些全局函数的相关知识,内容详细易懂,操作简单快捷,具有一定借鉴价值,相信大家阅读完这篇Node.js环境提供了哪些全局函数文章都会有所收获,下面我们一起来看看吧。一、Node.js 下的全局函数1.1JavaScri…
免责声明:本站发布的图片视频文字,以转载和分享为主,文章观点不代表本站立场,本站不承担相关法律责任;如果涉及侵权请联系邮箱:360163164@qq.com举报,并提供相关证据,经查实将立刻删除涉嫌侵权内容。