[P1082][NOIP2012] 同余方程 (扩展欧几里得/乘法逆元)

最近想学数论

刚好今天(初赛上午)智推了一个数论题

我屁颠屁颠地去学了乘法逆元

然后水掉了P3811P2613

(zcy吊打集训队!)(逃

然后才开始做这题。

乘法逆元

乘法逆元的思路大致就是a*x恒等于1(mod b)满足a,b互质,则x为a的逆元

这里给一个P2613的函数

void exgcd(int a, int b, int &d, int &x,int &y)
{
if (b == ) {
d = a;
x = ;
y = ;
return;
}
exgcd(b, a%b, d, x, y);
int t = y;
y = x - (a / b)*y;
x = t;
}

还有一个线性算法,就是适合P3811的

a[i] = (p-p/i)*a[p%i]%p;//zcyddjxd

大致就是这两种了

本蒟蒻在数学一本通上看的线性貌似是a[i] = -(p/i)*a[p%i]%p; 看起来用在这里不行

思路

上面介绍了一下乘法逆元的算法,其中第一种就是扩展欧几里得的出来的

我这里引用@huangdu233 大佬的题解的分析(我自己推导不来,只会插模板)

求解不定方程a*x+b*y==gcd(a,b);
先给个解法推导吧:
∵a=[a/b]*b+a%b;
又∵欧几里得知:gcd(a,b)==gcd(b,a%b);
∴([a/b]*b+a%b)*x+b*y=gcd(a,b);
∴[a/b]*b*x+(a%b)*x+b*y=gcd(a,b);
∴b*([a/b]*x+y)+(a%b)*x=gcd(b,a%b);
看到这里,我们不难发现:
令:a'=b,x'=[a/b]*x+y,b'=a%b,y'=x;
整理后原式又变成了:a'*x'+b'*y'==gcd(a',b');
当当当当!!!!!可以递归了

废话了那么多,我就直接给代码吧

#include<bits/stdc++.h>
#define ll long long
#define mod 19260817
#define MAXN 10010
using namespace std;
ll a,b,x,y;
void exgcd(ll a, ll b, ll &x, ll &y)
{
if (b == ) {
x = ;
y = ;
return;
}
exgcd(b, a%b, y, x);
y -= (a / b)*x;
}
int main()
{
cin >> a >> b;
exgcd(a, b, x, y);
cout << (x + b) % b;
}

(刚用上VisualStudio 感觉还行)

注意

刚发现hl大佬写了这题的题解!

https://www.luogu.org/blog/hl666/solution-p1082

Orz 太强了

上一篇:mysql 的REPLAYCE语句


下一篇:kvm虚拟化管理平台WebVirtMgr部署-完整记录(安装Windows虚拟机)-(4)