#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
ll a,b;




ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1;y=0;
        return a;
    }
    ll ret=exgcd(b,a%b,x,y);
    ll buf=x;x=y;y=buf-a/b*y;
    return ret;
}


int main()
{
    scanf("%lld%lld",&a,&b);
    ll x,y;
    ll gcd=exgcd(a,b,x,y);
  x=(x%b+b)%b;
    printf("%lld",x);
}

很裸的扩欧

#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cctype>
#include <vector>
#include <queue>
using namespace std;
int a,b,x,y,k;
void gcd(int m,int n)
{
    if(n==0)
    {
        x=1;
        y=0;
        return;
    }
    gcd(n,m%n);
    k=x;
    x=y;
    y=k-m/n*y;
    return;
}
int main()
{
    scanf("%d%d",&a,&b);
    gcd(a,b);
    printf("%d",(x+b)%b);
    return 0;
}

pow(a, -1, b) # Python 3.8

扩欧

#include<cstdio>
#include<cmath>
using namespace std;
typedef long long LL;
void gcd(LL a, LL b, LL &d, LL &x, LL &y) {
    if (!b) {d = a, x = 1, y = 0;}
    else {gcd(b, a % b, d, y, x); y -= x * (a / b); }
}
int main() {
    LL a, b, GCD, x, k;
    scanf("%lld %lld", &a, &b);
    gcd(a, b, GCD, x, k);
    LL ta = b / GCD;
    while (x < 0) x += ta;
    printf("%lld", x);
    return 0;
}

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
using namespace std;

long long ext_gcd_1(long long a,long long b,long long &x,long long &y)
{
    if (b==0)
    {
        x=1,y=0;
        return a;
    }
    else
    {
        long long ans=ext_gcd_1(b,a%b,x,y);
        long long temp=x;
        x=y;
        y=temp-(a/b)*y;
        return ans;
    }
}

long long a,b,x,y;

int main()
{
    scanf("%lld%lld",&a,&b);
    long long temp=ext_gcd_1(a,b,x,y);
    printf("%lld\n",(x+b)%b);
}

#include <iostream>
#include <algorithm>
using namespace std;
#define For(aHJEfaks, fwbjkWK, AENGIBv) for (int aHJEfaks = fwbjkWK; aHJEfaks <= AENGIBv; ++aHJEfaks)
#define For2(aHJEfaks, fwbjkWK, AENGIBv) for (auto aHJEfaks = fwbjkWK; aHJEfaks != AENGIBv; ++aHJEfaks)
long long a0, b0;
typedef pair<long long, long long> pa;
pa s(long long a, long long b){
    if (a == 1){
        return make_pair(1, 0);
    }
    if (b == 1){
        return make_pair(0, 1);
    }
    if (a > b){
        long long q = a / b;
        long long r = a % b;
        pa tms = s(r, b);
        return make_pair(tms.first, tms.second - q * tms.first);
    }
    if (a < b){
        long long q = b / a;
        long long r = b % a;
        pa tnm = s(a, r);
        return make_pair(tnm.first - q * tnm.second, tnm.second);
    }
}
int main(){
    cin >> a0 >> b0;
    long long tem = s(a0, b0).first;
    long long ans = 0;
    if (tem > 0) {
        ans = tem - (tem / b0) * b0;
    }
    if (tem < 0){
        ans = tem - (tem / b0 - 1) * b0;
    }
    cout << ans << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
void exgcd(int a, int b, int &x, int &y)
{
    if(a==1){
        x=1;y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    int temp=x;
    x=y;
    y=temp-a/b*y;
}
int main()
{
    int a,b,x,y;
    cin>>a>>b;
    exgcd(a,b,x,y);
    if(x<1)x+=b;
    cout<<x<<endl;
    system("pause");
    return 0;
}
//此题所用拓展欧几里得算法
//详见http://blog.csdn.net/zhjchengfeng5/article/details/7786595

裸地模板题，，

#include <algorithm>
#include  <iostream>
#include   <cstring>
#include    <cstdio>
#include     <cmath>
using namespace std;

void exgcd(int a, int b, int& x, int& y) {
    if(!b) { x = 1; y = 0; return; } 
    int q = a/b, r = a%b;
    exgcd(b, r, y, x);
    y -= q*x;
}

int inv (int a, int b) {
    int x, y;
    exgcd(a, b, x, y);
    return x;
}

int main() {
    
    int n, Mod;
    scanf("%d%d", &n, &Mod);
    int sum = inv(n, Mod);
    if(sum < 0) sum += Mod;
    printf("%d", sum);
    
    return 0;
}

#include <iostream>
#include <cstdio>
#include <algorithm>
#define rep(i,n) for(i=1;i<=n;i++)
using namespace std;
void exgcd(int a, int b, int &x, int &y){
if(b==0){
x = 1; y = 0;
return;
}
exgcd(b,a%b,y,x);
y -= a/b*x;
}
int main(){
int i, j, n, m, a, b;
scanf("%d%d", &a, &b);
exgcd(a,b,n,m);
printf("%d",(n+b)%b);
return 0;
}
exgcd求逆元裸题= =

program
    emod;

uses
    math;

var
    a, b, x, y: longint;

procedure egcd(a, b: longint; var x, y: longint);
var
    temp: longint;
begin
    if b = 0 then
    begin
        x := 1;
        y := 0;
        exit;
    end;
    egcd(b, a mod b, x, y);
    temp := x;
    x := y;
    y := temp - (a div b) * y;
end;

begin
//    assign(input, 'mod.in'); assign(output, 'mod.out');
//    reset(input); rewrite(output);
    read(a, b);
    egcd(a, b, x, y);
    while x < 0 do
        inc(x, b);
    write(x);
//    close(input); close(output);
end.

C++题解+代码
http://www.cnblogs.com/937337156Zhang/p/5697140.html

强行不用exgcd（虽然复杂度加了个sqrt()）
由欧拉定理得,如果a和n互质，那么

a^phi(n) 同余 1(mod n)
所以
a^(phi(n)-1) 就是a在mod n意义下的乘法逆元
算phi是O(sqrt(n))的
快速幂是O(logn)的
总复杂度O(sqrt(n))

#include<bits/stdc++.h>
using namespace std;
inline int phi(int x)
{
    int tail = sqrt(x) + 1e-6;
    int ans = x;
    for (int i = 2;i <= tail;i++)
    {
        if (!(x % i))
        {
            ans = ans / i *(i - 1);
            while (!(x%i))x /= i;
        }
    }
    if (x != 1)ans = ans / x *(x - 1);
    return ans;
}
int mod;
int qpow(int x, int y)
{
    if (y == 0)return 1;
    if (y == 1)return x;
    if (y == 2)return (long long)x*x%mod;
    if (y == 3)return (long long)x*x%mod*x%mod;
    int tmp = qpow(x, y >> 1);
    tmp = (long long)tmp * tmp % mod;
    if (y & 1)tmp = (long long )tmp * x % mod;
    return tmp;
}
int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    mod = b;
    printf("%d\n", qpow(a, phi(b) - 1));
}

#include <iostream>
using namespace std;

void gcd(int a, int b, int& x, int& y){
    if(b != 0){
      gcd(b, a%b, x, y);
      int r = x;
      x = y;
      y = r - (a / b) * x;
    }
    else
      x = 1, y = 0;
}

int main(){
    int a, b, x, y;
    cin>>a>>b;
    gcd(a, b, x, y);
    cout<<(x + b) % b<<endl;
    return 0;
}

#include <iostream>
using namespace std;

void ex_gcd(int a, int b, int& x, int& y){
    if(b != 0){
      ex_gcd(b, a%b, x, y);
      int bri = x;
      x = y;
      y = bri - (a / b) * x;
    }
    else
      x = 1, y = 0;
}

int main(){
    int a, b, x, y;
    cin>>a>>b;
    ex_gcd(a, b, x, y);
    cout<<(x + b) % b<<endl;
    return 0;
}

#include <iostream>
using namespace std;

void ex_gcd(int a, int b, int& x, int& y){
if(b != 0){
ex_gcd(b, a%b, x, y);
int bri = x;
x = y;
y = bri - (a / b) * x;
}
else
x = 1, y = 0;
}

int main(){
int a, b, x, y;
cin>>a>>b;
ex_gcd(a, b, x, y);
cout<<(x + b) % b<<endl;
return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long LL;

void gcd (LL a, LL b, LL &d, LL &x, LL &y) {
    if (!b) { d = a; x = 1; y = 0;}
    else { gcd(b, a%b, d, y, x); y -= x*(a/b);}
}

int main ()
{
    freopen("in.txt", "r", stdin);
    LL a, b;
    cin >> a >> b;
    LL d, x, y;
    gcd(a, b, d, x, y);
    if(x < 0) while (x < 0) x += b;
    else while (x > b) x -= b;
    cout << x;
    return 0;
}

var
a,b,x:longint;
begin
read(a,b);
x:=1;
while (a*x) mod b<>1 do begin
x:=x+1;
end;
writeln(x);
end.

var
a,b,x:longint;
begin
read(a,b);
x:=1;
while (a*x) mod b<>1 do begin
x:=x+1;
end;
writeln(x);
end.

同余方程都不知道 ，咋做
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int x,y;
void gcd(int a,int b)
{
if (a%b==0)
x=0,y=1;
else
{
gcd(b,a%b);
int t=x;
x=y,y=t-(a/b)*y;
}
}
int main()
{
int a,b;
cin>>a>>b;
gcd(a,b);
cout<<(x%b+b)%b;
}

就是求乘法逆元，拓展欧几里得算法。
~~~
#include <cstdio>
int exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1;
y=0;
return a;
}
int ans=exgcd(b,a%b,x,y);
int temp=x;
x=y;
y=temp-(a/b)*y;
return ans;
}
int main(){
int a,b,x,y;
scanf("%d%d",&a,&b);
exgcd(a,b,x,y);
while(x<=0)x+=b;
printf("%d\n",x);
}