标签：数论，扩展欧几里得
题目描述
求关于 x 的同余方程 ax ≡ 1(mod b)的最小正整数解。
输入输出格式
输入格式：
输入只有一行，包含两个正整数 a, b，用一个空格隔开。
输出格式：
输出只有一行，包含一个正整数 x0，即最小正整数解。输入数据保证一定有解。
输入输出样例
输入样例#1： 复制
3 10
输出样例#1： 复制
7
说明
【数据范围】
对于 40%的数据，2 ≤b≤1,000；
对于 60%的数据，2 ≤b≤50,000,000；
对于 100%的数据，2 ≤a, b≤2,000,000,000。
NOIP 2012 提高组 第二天 第一题
扩欧裸题
关于扩欧的证明https://www.zybuluo.com/samzhang/note/541890
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define LL long long
using namespace std;
inline LL read()
{
LL f=1,x=0;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;
}
LL a,b;
void exgcd(int a,int b,LL &x,LL &y){
if(b==0){x=1,y=0;return;}
exgcd(b,a%b,x,y);
LL t=x;
x=y,y=t-a/b*y;
}
int main()
{
a=read(),b=read();
LL x,y;
exgcd(a,b,x,y);
cout<<(x+b)%b<<endl;
return 0;
}
