思路

简单的逆元入门题.
如果是质数,直接用费马小定理求解即可.
这里不一定是质数,所以要用.
设存在整数使得.那么很明显.
因此只要解出即可.直接用求出一组可行解,对取模即可.这里保证有解,因此不用判断是否为.
复杂度为,也就是的复杂度.

代码

#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i )
#define go( i, b ) for ( int i(b), v(to[i]); i; v = to[i = nxt[i]] )
template<typename T> inline void cmax( T &x, T y ){ x < y ? x = y : x; }
template<typename T> inline void cmin( T &x, T y ){ y < x ? x = y : x; }
template<typename T>
inline void read( T &x ){ char t(getchar()), flg(0); x = 0;
    for ( ; !isdigit(t); t = getchar() ) flg = t == '-';
    for ( ; isdigit(t); t = getchar() ) x = x * 10 + ( t & 15 );
    flg ? x = -x : x;
}

clock_t t_bg, t_ed;

i64 a, b, x, y;

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

int main(){
    t_bg = clock();
    read(x), read(y), exgcd( x, y, a, b ), printf( "%lld\n", (a % y + y) % y );
    t_ed = clock();
    fprintf( stderr, "\n========info========\ntime : %.3f\n====================\n", (double)( t_ed - t_bg ) / CLOCKS_PER_SEC );
    return 0;
}