扩展欧几里得应用2（数论）

题目描述

【题意】
已知a,b,m,求x的最小正整数解，使得ax=b(mod m)
【输入格式】
一行三个整数 a，b，m。 1 ≤ a,b,m ≤ 10^9 
【输出格式】
一行一个整数x，无解输出"no solution!"
【样例输入】
2 5 7
【样例输出】
6

解释：

这题通俗讲就是 ax mod m=b mod m
那么 b 是个常数，所以直接 b=b%m，不影响结果

ax%m=b%m
ax−⌊ax/m⌋×m=b
ax+m×(−⌊ax/m⌋)=b
然后两边都有 x 怎么办？
直接当作 x 和 y 的某种关系即可，因为我们只要求 x。

Ax+By=K
A=a,B=m,K=b

这里注意他要求的是 最小正整数解

x 转最小非负整数解：
t=B/GCD------（这里并不是很懂为什么这样写 ， 先记着吧~）
x=(x%t+t)%t
举例：
初始：x=-1 y=1
2x+7y=5
t=B/GCD=7/1=7
最后：x=6 y=-1

代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL ExEuclid(LL a , LL b , LL &x , LL &y)
{
	if(b == 0)
	{
		x = 1;y = 0;
		return a;
	}
	LL tx , ty;
	LL d = ExEuclid(b , a%b , tx , ty);
	x = ty;
	y = tx - (a/b)*ty;
	return d ;
}
int main()
{
	LL a , b , m , x , y;
	LL A , B , K;
	scanf("%lld %lld %lld" , &a , &b , &m);
	K = b % m;
	A = a , B = m;
	LL d = ExEuclid(A , B , x , y);
	if(K % d != 0)
	{
		printf("no solution!\n");
	}
	else
	{
		x = x * K / d;
		LL t = B / d;
		LL xx = (x % t + t)%t;
	//	y = (K - A * x) / B;
		printf("%lld\n" , xx);
	}
	return 0;
}