5/11日奥数

上半节

1.形式分数法:

2.例子:

解法:

3.扩展欧几里得算法(EXEA)

1.背景

2.步骤如下:

3.扩展欧几里得算法代码实现:

#include <iostream>
#include <tuple>

using namespace std;
tuple<int, int, int> gcdd(int a, int b) {
    if (b == 0) {
        return {a, 1, 0}; // gcd = a, x = 1, y = 0
    }
    
    int gcd, x1, y1;
    tie(gcd, x1, y1) = gcdd(b, a % b);
    
    int x = y1;
    int y = x1 - (a / b) * y1;
    
    return {gcd, x, y};
}

int main() {
    int a , b ;
    int gcd, x, y;
    cin>>a>>b;
    tie(gcd, x, y) = gcdd(a, b);
    
    cout << "gcd(" << a << ", " << b << ") = " << gcd << endl;
    cout << "贝祖系数: x = " << x << ", y = " << y << endl;
    cout << "验证: " << a << " * " << x << " + " << b << " * " << y << " = " << a * x + b * y << endl;
    
    return 0;
}    

4.拓展欧几里得算法求同余方程的解:

5.拓展欧几里得算法求同余方程的解代码实现:

#include <iostream>
#include <vector>
#include <tuple>

using namespace std;

// 扩展欧几里得算法：计算gcd(a, b)以及满足ax + by = gcd(a, b)的贝祖系数x和y
tuple<int, int, int> extendedGCD(int a, int b) {
    if (b == 0) {
        return {a, 1, 0};
    }
    
    int gcd, x1, y1;
    tie(gcd, x1, y1) = extendedGCD(b, a % b);
    
    int x = y1;
    int y = x1 - (a / b) * y1;
    
    return {gcd, x, y};
}

// 求解同余方程 ax ≡ b (mod m)
vector<int> solveCongruence(int a, int b, int m) {
    vector<int> solutions;
    
    // 处理a或b为负数的情况，转换为模m下的正数
    a = (a % m + m) % m;
    b = (b % m + m) % m;
    
    int gcd, x, y;
    tie(gcd, x, y) = extendedGCD(a, m);
    
    // 检查方程是否有解：gcd(a, m) 必须整除 b
    if (b % gcd != 0) {
        return solutions; // 无解，返回空向量
    }
    
    // 计算特解
    int x0 = (x * (b / gcd)) % m;
    if (x0 < 0) x0 += m; // 确保特解为正数
    
    // 生成所有解
    for (int i = 0; i < gcd; i++) {
        int solution = (x0 + i * (m / gcd)) % m;
        solutions.push_back(solution);
    }
    
    return solutions;
}

int main() {
    int a,b,m;
    cin>>a>>b>>m;
    
    cout << "求解同余方程: " << a << "x ≡ " << b << " (mod " << m << ")" << endl;
    vector<int> solutions = solveCongruence(a, b, m);
    
    if (solutions.empty()) {
        cout << "无解" << endl;
    } else {
        cout << "共有 " << solutions.size() << " 个解:" << endl;
        for (int i = 0; i < solutions.size(); i++) {
            cout << "解 " << i+1 << ": x ≡ " << solutions[i] << " (mod " << m << ")" << endl;
        }
    }
    
    return 0;
}       

时间复杂度为

4.例子:

解:

说明:

5.引理:

6.威尔逊定理

证明:

再例: