逆元； ab=1(mod mo) 在mo的模域下ab互为倒数； 这样你除a和乘b就是一样的； 本来关于exgcd求逆元的东西我要在后面写； 但是有一道题目，要一边除一遍取模，然后我的同学全用分解质因数，没有人用逆元，就问他们可不可以用逆元 答
题解就是分解质因数啊，逆元也可以把
麻木潦倒； 为什么他们考试都比我好呢？ 一定是我太傻了； 我们根据ab=1(mod mo) 是不是可以变成 ab-y*mo=1(mod ∞) 那么我们知道a，知道mo，而且gcd（a，mo）=1 我们是不是可以用exgcd求b了？ ac+y*mo=1; 原来exgcd也是有条件的，所以逆元应用并不是怎么广泛啊 https://www.luogu.org/problem/show?pid=1082 裸题
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #include<cstring> #include<map> #define Ll long long using namespace std; void exgcd(Ll a,Ll b,Ll &x,Ll &y){ if(!b){x=1;y=0;return;} exgcd(b,a%b,x,y); Ll X=x; x=y; y=X-a/b*y; } int main() { Ll n,m; scanf("%lld%lld",&n,&m); Ll x,y; exgcd(n,m,x,y); x=(x%mo+mo)%mo; printf("%lld",x); }