NOIP2012同余方程

题目描述

求关于$x$的同余方程 $ax\equiv 1(\mathrm{mod}b)$ 的最小正整数解。

输入格式

一行，包含两个正整数 $a,b$，用一个空格隔开。

输出格式

一个正整数 $x_0$，即最小正整数解。输入数据保证一定有解。

样例 #1

样例输入 #1

3 10

样例输出 #1

7

提示

【数据范围】

对于 40%的数据，$2\le b\le 1,000$；

对于 60%的数据，$2\le b\le 50,000,000$；

对于 100%的数据，$2\le a,b\le 2,000,000,000$。

NOIP 2012 提高组 第二天 第一题

题解

很容易想到一种朴素做法，暴力枚举$x$
能骗60分

......
cin >> a >> b;
int i;
for(i=1;;i++)
	if(a*i%b==1)
		break;
cout << i;
......

正解

扩展欧几里得算法
$ax\equiv 1(\mathrm{mod}b)$
可推出
$ax+by=1(y为整数)$
若$a,b$互质，则可用扩欧解此方程
当然题目保证一定有解，故无需考虑此情况
注意求的是$x$的最小正整数解，故需
$(x\%b+b)\%b$

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll x,y;
ll exgcd(ll a,ll b){
    
	if(!b){
    x = 1; y = 0; return a;}
	ll d = exgcd(b,a%b);
	ll z = x; x = y; y = z-(a/b)*y;
	return d;
}
int main(){
    
	ll a,b;
	cin >> a >> b;
	exgcd(a,b);
	cout << (x%b+b)%b;
	return 0;
}