乘法逆元 hdu 1576 A/B

本文主要是介绍乘法逆元 hdu 1576 A/B，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

乘法逆元在除法取模运算中有着广泛的应用。
百度百科：
费马小定理(Fermat Theory)是数论中的一个重要定理，其内容为： 假如p是质数，且Gcd(a,p)=1，那么 a(p-1) ≡1（mod p）。即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。
例如：a=5,p=7,满足p是质数，a,p互质的要求，因此有5^6%7=1.  又如：a=8,p=7-->8^6%7=1.
百度百科：
欧拉函数：在数论中，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。φ函数的值 　通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数(小于等于1)就是1本身）。 【注意：每种质因数只一个。比如12的相关互质数有：1,5,7,11。12=2*2*3那么φ（12）=12*（1-1/2）*(1-1/3)=4】。
欧拉函数的通式有容斥原理的影子，这样理解吧。
phi[x]=φ(x).

a^phi(P)=1(mod P)

例如：a=5,p=7 --> 5^6%7=1;   a=8,p=7 --> 8^6%7=1

所以：a^(phi(P)-1) mod P即为a在模P意义下的乘法逆元。

证明乘法逆元的替代作用：（令k是b的乘法逆元）
a*b' mod p =a/b mod p.
过程：
b*b'≡1 (mod p)-->b*b'=p*x+1。
b'=(p*x+1)/b。
把b'代入(a*b') mod p，得：
(a*(p*x+1)/b) mod p
=((a*p*x)/b+a/b) mod p
=((a*p*x)/b) mod p +(a/b) mod p
=(p*(a*x)/b) mod p +(a/b) mod p
因为：p*[(a*x)/b] mod p=0
所以：(a*b') mod p 《--》 (a/b) mod p
转化的理由：
乘法的运算速度会比除法快4倍左右，在现有的Intel指令集中，就属除法指令最慢。
模运算性质:(a+b) % c=(a % c + b % c) %c , (a-b) % c=(a % c - b % c) % c, (a*b) % c=(a % c * b % c) % c,a ^ b % c = ((a % c)^b) % c。遗憾的是除法没有这个性质.
除法取模运算有时得到的结果是错误的（逆元正确）
例子：
a/b mod p 其中a=第一行数，b等于2，p=1e9+7。第二行是a*b'%p，第三行是a/b%p。
56346393
528173200
28173196

452192616
226096308
226096308

求解逆元，有拓展欧几里得和欧拉函数，另外用费马小定理结合快速幂取模同样也能迅速达到目的。
例子：
hdu 1576 A/B： http://acm.hdu.edu.cn/showproblem.php?pid=1576

#include <iostream>
#include<cstdio>
using namespace std;
typedef long long LL;
const LL mod=9973;
LL quick_mod(LL a,LL b){LL ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;
}
int main()
{int t;cin>>t;while(t--){int n,b;scanf("%d%d",&n,&b);LL ni=quick_mod(b,mod-2);printf("%lld\n",n*ni%mod);}return 0;
}

如果mod不是质数,或者gcd(b,mod)!=1，那么就需要用欧拉函数或者欧几里得拓展来求解逆元：

欧拉函数的求解：

#include <iostream>
#include<cstdio>
using namespace std;
typedef long long LL;
const LL mod=9973;
LL quick_mod(LL a,LL b){LL ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;
}
LL Euler(LL p){LL ans=p;for(int i=2;i*i<=p;i++){if(p%i==0){while(p%i==0)p/=i;ans=ans/i*(i-1);}}if(p>1)ans=ans/p*(p-1);return ans;
}
int main()
{//freopen("cin.txt","r",stdin);int t;cin>>t;while(t--){int n,b;scanf("%d%d",&n,&b);LL ni=quick_mod(b,Euler(mod)-1);printf("%lld\n",n*ni%mod);}return 0;
}

拓展欧几里得的逆元求解可以查看另一篇博客： http://blog.csdn.net/thearcticocean/article/details/47207799

 

这篇关于乘法逆元 hdu 1576 A/B的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---