/*
我在提交的时候发现了一个特别好玩的事,有兴趣的话,可以自己尝试一下;
把下面说的地方的y=0改为y=1在codevs里面能够ac,这……数据水?到一定境界……
厉害了,吓得我还以为自己对了,
结果一讲才知道,根本不对,
然后我自己自己弄数据它就不同,
这是……
我太厉害了?
哈哈哈
*/
题目描述 Description
求关于 x 同余方程 ax ≡ 1 (mod b)的最小正整数解。
输入描述 Input Description
输入只有一行,包含两个正整数 a, b,用 一个 空格隔开。
输出描述 Output Description
输出只有一行包含一个正整数x0,即最小正整数解,输入数据保证一定有解。
样例输入 Sample Input
3 10
样例输出 Sample Output
7
数据范围及提示 Data Size & Hint
【数据范围】
对于 40% 的数据, 2 ≤b≤ 1,000 ;
对于 60% 的数据, 2 ≤b≤ 50,000,000
对于 100% 的数据, 2 ≤a, b≤ 2,000,000,000
分类标签 Tags 点此展开
#include<cmath>
#include<cstdio>
#include<iostream> using namespace std; long long exgcd(long long a,long long b,long long &x,long long &y)
{
if(b==)
{
x=;
y=;//把这里的y=0改为y=1在codevs里面能够ac,这……数据水?到一定境界……
return a;
}
else{
long long r=exgcd(b,a%b,x,y),t=x;
x=y;y=t-a/b*y;
return r;
}
} int main()
{
long long a1,b1,x1,y1;
cin>>a1>>b1;
exgcd(a1,b1,x1,y1);
while(x1<) x1+=b1;
cout<<x1;
return ;
}