同餘方程

題目描述

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

輸入輸出格式

輸入格式：

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

輸出格式：

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

【資料範圍】

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

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

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

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int x,y,a,b,t;
void exgcd(int a,int b)
{

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

}
int main()
{

    scanf("%d%d",&a,&b);
    exgcd(a,b);
    printf("%d",(x+b)%b);

}