AcWing 878. 线性同余方程
给定 $n$ 组数据 $a_i,b_i,m_i$,对于每组数求出一个 $x_i$,使其满足 $a_i \times x_i \equiv b_i \pmod {m_i}$,如果无解则输出 impossible
。
输入格式
第一行包含整数 $n$。
接下来 $n$ 行,每行包含一组数据 $a_i,b_i,m_i$。
输出格式
输出共 $n$ 行,每组数据输出一个整数表示一个满足条件的 $x_i$,如果无解则输出 impossible
。
每组数据结果占一行,结果可能不唯一,输出任意一个满足条件的结果均可。
输出答案必须在 $int$ 范围之内。
数据范围
$1 \le n \le 10^5$,
$1 \le a_i,b_i,m_i \le 2 \times 10^9$
输入样例:
2
2 3 6
4 3 5
输出样例:
impossible
-3
题解
思路
我们将题目里的方程转化一下
$a_i \times x_i \equiv b_i \pmod {m_i}$
$↓$
$(a_i \times x_i) \mod {m_i} = b_i$
$↓$
$a_i \times x_i = m_i \times y_i + b_i$ $(y_i = (a_i \times x_i) / m_i)$
$↓$
$a_i \times x_i - m_i \times y_i = b_i$
$↓$
$a_i \times x_i + (-m_i) \times y_i = b_i$
观察到这个方程的特殊性了吗?
与扩展欧几里得方程一样!
$a_i \times x_i + b_i \times y_i = gcd(a_i, b_i)$ $a_i \times x_i + (-m_i) \times y_i = b_i$
也就是说当$b_i$是$a_i$和$m_i$的公约数$gcd(a_i, b_i)$的倍数方程就成立,也就是$b_i = k \times gcd(a_i, b_i)$ $k = 1, 2, ···$
- 由扩展欧几里得方程我们知道,下一层的$gcd(b_i, a_i \mod b_i) $ $x’ = x$,$x$不会改变, $y’ = y - \lfloor\frac{a}{b}\rfloor \times x$
- 本题只求最终递归完成后的系数$x$,符合要求的答案$x$不止一个,求出来的可能不一样
代码实现
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a, m, b, x, y;
int exgcd(int a, int b, int &x, int &y)
{
if (!b) //找到了公约数
{
x = 1, y = 0;
return a;
}
int gcd = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return gcd;
}
void solve()
{
cin >> a >> b >> m;
int gcd = exgcd(a, -m, x, y);
//cout << m << endl;
if (b % gcd != 0) //如果b不是 a和m公约数gcd 的k倍
{
cout << "impossible" << endl;
}
else
{
int k = b / gcd; //当b是gcd(a, m)的k倍,那么等式另一边的x和y也要乘上k倍,等式才成立
cout << x * k % m << endl; //%m保证答案在int范围内
}
return;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie();
cin >> n;
while(n -- )
{
solve();
}
return 0;
}
- 一个特殊点说明
c++
cout << x * k % m << endl; //%m保证答案在int范围内
这里为了保证x * k
在int
范围内,mod上k
,那为什么可以mod k呢,观察题目, $a_i \times x_i \equiv b_i \pmod {m_i}$,模上m后x也是满足这个式子的,因为符合这个式子的答案x不止一个,我们取出较小的就行