EOJ 题解 | 1056.线性同余方程（扩展欧几里得 C++）

捡起一束光

于 2020-05-21 09:46:44 发布

阅读量330

点赞数

分类专栏： AI算法工程师

本文链接：https://blog.csdn.net/qq_43827595/article/details/106249993

版权

AI算法工程师专栏收录该内容

48 篇文章

订阅专栏

本文详细介绍了扩展欧几里得算法的应用，通过求解线性方程组找到特解，并利用该算法解决模数下的一系列数学问题。代码示例展示了如何使用C++实现算法，包括输入输出流程。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

原题链接
在这里插入图片描述
解题思路
扩展欧几里得算法求出一组特解，然后 $0\sim m-1$ 中共有 $(a, m)$ 个解

#include <iostream>

using namespace std;

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 a, b, m;
    // ax + my = b
    while (cin >> a >> b >> m) {
        int x, y;
        int d = exgcd(a, m, x, y);
        if (b % d != 0) cout << "No Answer." << endl;
        else {
            x *= b / d; // 特解x'
            // x = x' + k*m/d
            int t = m / d;
            x = (x % t + t) % t;
            for (int i = 0; i < d; i++) {
                cout << x << " ";
                x += t;
            }
            cout << endl;
        }
    }
    return 0;
}