AcWing 878. 线性同余方程
原题链接
简单
作者：
sjytker
,
2019-11-06 21:17:03
,
所有人可见
,
阅读 8883
- 因为 $ a * x \equiv b (mod\ m) $ 等价于 $ a * x - b $ 是m的倍数，因此线性同余方程等价为 $ a * x + m * y = b$
- 根据 Bezout 定理，上述等式有解当且仅当 $gcd(a, m) | b$
- 因此先用扩展欧几里得算法求出一组整数 $x_0, y_0$, 使得 $a * x_0 + m * y_0 = gcd(a, m)$。 然后 $x = x_0 * b / gcd(a, m) \% m$ 即是所求。
#include<bits/stdc++.h>
using namespace std;
int n, x, y;
using LL = long long ;
int exgcd(int a, int b, int &x, int &y)
{
if (!b)
{
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, x, y);
int z = x;
x = y;
y = z - a / b * y;
return d;
}
int main()
{
cin >> n;
while (n --)
{
int a, b, m;
cin >> a >> b >> m;
int d = exgcd(a, m, x, y);
if (b % d) puts("impossible");
else
{
x = (LL)x * b / d % m;
cout << x << endl;
}
}
return 0;
}
为什么是这个公式啊x=x0∗b/gcd(a,m)%m
证明的时候等式右侧是gcd(a,m),实际求得是b，b是gcd(a,m)的倍数，当把gcd(a,m)扩大到b时，对应的x和y也应该扩大
为什么要%m呢？
答案要求在int范围内，ai×xi≡bi(modmi)能推出ai×(xi%mi)≡bi(modmi)
gcd应该是小的，其k倍为b的情况下有解
就喜欢这种干净的证明
请问为什么最后一步要%m呢（x = (LL)x * b / d % m;），不能直接输出前面的内容吗？？？
题目中要求“输出答案必须在int范围之内”，而算到的
x可能会溢出，根据(a*x) % m = (a * (x % m)) % m，所以保险起见输出为x % m那再请问一下为什么只能%m，不能模个其他的数，比如说%int的值
题目要求$a_{i} * x_{i} \equiv b_{i}(mod m_{i}) $,只有
x%m这个等式才依然成立.x的通解为：x = x0 + m/gcd(a,m)*k(k为整数)，视频里有提到通解
所以所对于任意解x的模上m/gcd(a,m)都成立，当然模上m也是成立的
从而可以推出最小正整数解为：（x0%(m/gcd(a,m) + (m/gcd(a,m) ) %(m/gcd(a,m),,,(防止x0为负数)
相当于求一组特解，然后求通解，%m是为了让该解符合题意。
请问一下，为什么不直接x mod m呢?
简单明了%%%%%
有解当且仅当 gcd(a,m)|b，那这步不是有问题吗if (b % d) puts(“impossible”);
gcd最大公约数，是小的数字，b是大的数字，是gcd的k倍，情况下视作有解
整除可以的话取mod是0就不会触发impossible
当a=4,b=3,m=5时为什么x可以等于 -3 呢？4 乘 (-3) 模上5等于 -2，和b=3也不符合
？？？对啊现在-3这个数据好奇怪
啊-12 % 3 不是等于3咩
-2%5 = 3
为什么最后要%m呢x=x0∗b/gcd(a,m)%m
题目中要求“输出答案必须在int范围之内”，而算到的x可能会溢出，根据(a*x) % m = (a * (x % m)) % m，所以保险起见输出为x % m
为什么%m不会影响结果呢
看看我的评论有说的
aixi≡bi(mod mi)意思是求一个x使得a乘以x除以m的余数是b（也就是模上m等于b）即(ax)/m的余数是b
如果x是m的k(k可以是小数)倍那么把x%m不影响b的大小，所以题目要求在int范围，所以最后把x%m即可
有道理
谢谢大佬，看懂了
x = (LL)x * b / d % m;为什么%m而不是%a或者%b
题目中要求“输出答案必须在int范围之内”，而算到的x可能会溢出，根据(a*x) % m = (a * (x % m)) % m，所以保险起见输出为x % m
tql
这是题意就是mod m 吧， 如果是保险起见那不是mod任何一个 int型的数就行了？
肯定不能随便模一个数啊，这里x的通解是x=x0-m/d*k，所以通过exgcd函数得到的x0 mod m后得到的新的x仍是通解范围内的一个解，你随便模别的数得到的x就不是解了啊
tql
老哥，我想问下这里为什么不能直接输出x0呢
题目中要求“输出答案必须在int范围之内”