数论—快速幂，欧几里得及其扩展，逆元，单位元_数论单位元函数-CSDN博客
之前做的数论笔记👆👆👆
题目一：扩展欧几里得算法
877. 扩展欧几里得算法 - AcWing题库
分析
代码
#include<bits/stdc++.h>
using namespace std;int exgcd(int &x, int &y, int a, int b) {if(!b) {x = 1;y = 0;return a;}int c = exgcd(x,y,b,a%b);int t = y;y = x-(a/b)*y;x = t;return c;
}int main() {int _;cin >> _;while(_ --) {int a, b; cin >> a >> b;int x, y;int c = exgcd(x,y,a,b);cout << x << " " << y << endl;}return 0;
}题目二：线性同余方程
878. 线性同余方程 - AcWing题库
分析
代码
#include<bits/stdc++.h>
using namespace std;using ll = long long;int exgcd(int &x, int &y, int a, int b) {if(b == 0) {x = 1, y = 0;return a;}int d = exgcd(x,y,b,a%b);int t = y; y = x-(a/b)*y; x = t;return d;
}int main() {int _;cin >> _;while(_ --) {int a, b, m;cin >> a >> b >> m;int x, y;int d = exgcd(x,y,a,m);if(b%d) puts("impossible");else {cout << (ll)x*b/d%m << endl; // 先乘后除开ll防爆数据 //答案要求在int 范围，a(modm)*x(modm)=b mod(m);}}return 0;
}
)
