最近想学数论

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

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

然后水掉了P3811 和 P2613

(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 == 0) { d = a; x = 1; y = 0; 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 == 0) { x = 1; y = 0; 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 太强了

转载于:https://www.cnblogs.com/lincold/p/9781750.html