acwing 878. 线性同余方程

目录

题目描述

给定 nn 组数据 ai,bi,mi,对于每组数求出一个 xi,使其满足 \(ai×xi≡bi(\%mi)\),如果无解则输出 impossible

输入格式

第一行包含整数 n。

接下来 n 行,每行包含一组数据 ai,bi,mi

输出格式

输出共 n 行,每组数据输出一个整数表示一个满足条件的 xi,如果无解则输出 impossible

每组数据结果占一行,结果可能不唯一,输出任意一个满足条件的结果均可。

输出答案必须在 int范围之内。

数据范围

1≤n≤105
1≤ai,bi,mi≤2×1091

输入样例:

2
2 3 6
4 3 5

输出样例:

impossible
-3

扩展欧几里得算法求解

分析

因为 $a∗x≡b(% m) $等价于 \(a∗x−b\) 是m的倍数,因此线性同余方程等价为 \(a∗x+m∗y=b\)
根据 Bezout 定理,上述等式有解当且仅当 \(gcd(a,m)|b\) (\(b整除 gcd(a,m)\))
因此先用扩展欧几里得算法求出一组整数 \(x0,y0\) 使得 \(a∗x0+m∗y0=gcd(a,m)\)。 然后$ x=x0∗b/gcd(a,m)%m$ 即是所求。

https://www.acwing.com/solution/content/5937/

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long LL;
// 返回 gcd(a,b)
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}


int main()
{
    int n;
    scanf("%d", &n);
    while(n --)
    {
        int a, b, m;
        scanf("%d%d%d", &a, &b, &m);
        int x, y;
        int d = exgcd(a, m, x, y);
        if(b % d) // b不能整除gcd(a,b),此时无解
        {
            printf("impossible\n");
        }
        else 
        {
            LL res = (LL) x * b / d % m;
            printf("%lld\n", res);
        }
    }
    return 0;
}

时间复杂度

参考文章

上一篇:LeetCode 42: 接雨水(困难)


下一篇:acwing 868. 筛质数