C - 곱셈 역 원 구 역 원

2 개의 수 M 과 N (M < N) 을 제시 하고 M 과 N 의 상호 질 을 제시 하여 하나의 수 K 를 찾 아 0 < K < N 및 K * M% N = 1 을 만족 시 키 고 여러 개의 만족 조건 이 있 으 면 수출 이 가장 적다.
Input
숫자 M 을 2 개 입력 하고 N 중간 에 빈 칸 으로 구분 (1 < = M < N < = 10 ^ 9)
Output
하나의 수 K 를 출력 하여 0 < K < N 및 K * M% N = 1 을 만족 시 키 고 여러 개의 만족 조건 이 있 으 면 출력 이 가장 적 습 니 다.
Sample Input

2 3

Sample Output

2

 
#include #include #include #include #include #include #include #include #include #define long long LL; #define INF 0x3f3f3f3f #define PI acos(-1.0) using namespace std; void exgcd(int a,int b,int &x,int &y) {     if(!b)     {         x=1;         y=0;         return ;     }     exgcd(b,a%b,x,y);     int t=x;     x=y;     y=t-(a/b)*y; } int main() {     int n,m,x,y;     cin>>n>>m;     exgcd(n,m,x,y);     printf("%d",(x+m)%m);     return 0; }