求关于x的同余方程ax ≡ 1 (mod b)的最小正整数解。

输入格式

输出格式

样例输入1[复制]

3 10

样例输出1[复制]

7

每个测试点1s

对于40%的数据，2 ≤b≤ 1,000； 
对于60%的数据，2 ≤b≤ 50,000,000； 
对于100%的数据，2 ≤a, b≤ 2,000,000,000。

Noip2012提高组复赛Day2T1

#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971using namespace std;inline LL read(){    LL x=0,f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}int a,b,x,y;inline int gcd(int a,int b){	if (!b)return a;	return gcd(b,a%b);}inline 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(){	a=read();b=read();	exgcd(a,b,x,y);	x=(x%b+b)%b;	printf("%d\n",x);}