同餘方程-NOIP2012TGD2T1

題目描述

題目描述

求關于x的同餘方程ax≡1(mod b)的最小正整數解。

輸入格式

每組輸入資料隻有一行，包含兩個正整數a, b，用一個空格隔開。

資料規模：

對于40%的資料，2≤b≤1,000；

對于60%的資料，2≤b≤50,000,000；

對于100%的資料，2≤a, b≤2,000,000,000。

輸出

每組輸出隻有一行，包含一個正整數x0，即最小正整數解。輸入資料保證一定有解。

樣例輸入

3 10

樣例輸出

7

輸入

輸出

提示

#include <cstdio>
void gcd(int a,int b,int& d,int& x,int& y){
    if(!b){d=a;x=1;y=0;}
    else{gcd(b,a%b,d,y,x);y-=x*(a/b);}
}

int inverse(int a,int b){
    int d,x,y;
    gcd(a,b,d,x,y);
    return (x%b+b)%b;
}

int main(){
    int a,b;
    while(scanf("%d%d",&a,&b)==2){
        printf("%d\n",inverse(a,b));
    }
    return 0;
}