题目描述
求关于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 提高组 第二天 第一题
数论的题吗。。。对于我这种菜鸡来讲真不适合用来写题解。。。
我们就把它背住就好了。。。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int a,b,x,y,k;
void exgcd(int a,int b)
{
if(b == 0)
{
x = 1;
y = 0;
return;
}
exgcd(b,a%b);
k = x;
x = y;
y = k - a/b*y;
return;
}
int main()
{
scanf("%d%d",&a,&b);
exgcd(a,b);
printf("%d",(x + b)%b);
return 0;
}
