大佬教程收集整理的这篇文章主要介绍了关于 exgcd求逆元 我的理解,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
我们有时会在求概率等或答案为分数的题目中遇到求逆元的情况
模板->航电 hd-1576
遇到了求(bf{frac{A}{B}})mod P 的问题
题目保证B和P互质
给出 n (A mod P 的值) 、B 、P
我们知道
但是
那该怎么办呢
我们可以想办法将它化成乘法形式 满足上面的第三个公式
学过倒数,我们想到了
那么,由上述的关于乘方取余数的式子得到
由题目得 A mod P 的值为 n
之后题目就转化成了 求 (frac{1}{B})mod P 的值
问题又来了 (frac{1}{B}) 的值该怎么求呢
它满足
所以定义 (frac{1}{B}) 叫做B关于P的逆(B也是 (frac{1}{B}) 关于P的逆元
可以表示为
继续进行式子的变形 上上一个式子等价于
到此就用到了扩展欧几里得 exgcd
这里使用exgcd就求出来 B 的逆元 了
接着返回题目中 用 B的逆元 乘 n 再对 P 取模就可了
通过这一波转化就可以把公式递归下去了
exgcd:
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){x=1;y=0;return a;}
ll tx=x,ty=y;
ll g=exgcd(b,a%b,tx,ty);
ll t=x;
x=ty;
y=tx-(a/b)*ty;
}
求逆元 (求 n 关于 m 的逆元):
ll exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1,y=0;
return a;
}
ll r = exgcd(b,a%b,x,y);
ll t = x;
x = y;
y = t - a/b*y;
return r;
}
ll inv(ll n,ll m){
ll x,y;
ll ans = exgcd(n,m,x,y);
if(ans == 1)
return (x%m+m)%m;
else
return -1;
}
hd-1576:
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1,y=0;
return a;
}
ll r = exgcd(b,a%b,x,y);
ll t = x;
x = y;
y = t - a/b*y;
return r;
}
ll inv(ll n,ll m){
ll x,y;
ll ans = exgcd(n,m,x,y);
if(ans == 1)
return (x%m+m)%m;
else
return -1;
}
int main(){
ll n,m;
ll t;
cin>>t;
while(t--){
cin>>n>>m;
ll ans = inv(m,9973);
cout<<(n*ans)%9973<<endl;
}
return 0;
}
以上是大佬教程为你收集整理的关于 exgcd求逆元 我的理解全部内容,希望文章能够帮你解决关于 exgcd求逆元 我的理解所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。