最近想学数论
刚好今天(初赛上午)智推了一个数论题
我屁颠屁颠地去学了乘法逆元
(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 太强了