描述
求关于x的同余方程ax ≡ 1 (mod b)的最小正整数解。
格式
输入格式
输入只有一行，包含两个正整数a, b，用一个空格隔开。
输出格式
输出只有一行，包含一个正整数x0，即最小正整数解。输入数据保证一定有解。
限制
每个测试点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<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
ll a,b,x,y;
void exgcd(ll aa,ll bb)
{
if(bb==0) {x=1; y=0; return;}
else
{exgcd(bb,aa%bb);
ll t=x;
x=y; y=t-aa/bb*y;
}
}
int main()
{
scanf("%lld%lld",&a,&b);
exgcd(a,b);//因为和y无关，所以可以看成ax+by=1
x=(x%b+b)%b;
if(!x) x=x+b;
printf("%lld\n",x);
return 0;
}