扩展欧几里得——acwing

数论—快速幂，欧几里得及其扩展，逆元，单位元_数论单位元函数-CSDN博客

之前做的数论笔记👆👆👆

题目一：扩展欧几里得算法

877. 扩展欧几里得算法 - AcWing题库

分析

代码

#include<bits/stdc++.h>
using namespace std;

int exgcd(int &x, int &y, int a, int b) {
    if(!b) {
        x = 1;
        y = 0;
        return a;
    }
    
    int c = exgcd(x,y,b,a%b);
    
    int t = y;
    y = x-(a/b)*y;
    x = t;
    
    return c;
}

int main() {
    int _;
    cin >> _;
    
    while(_ --) {
        int a, b; cin >> a >> b;
        int x, y;
        int c = exgcd(x,y,a,b);
        
        cout << x << " " << y << endl;
    }
    
    return 0;
}

题目二：线性同余方程

878. 线性同余方程 - AcWing题库

分析

代码

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

int exgcd(int &x, int &y, int a, int b) {
    if(b == 0) {
        x = 1, y = 0;
        return a;
    }
    
    int d = exgcd(x,y,b,a%b);
    
    int t = y; y = x-(a/b)*y; x = t;
    return d;
}

int main() {
    int _;
    cin >> _;
    while(_ --) {
        int a, b, m;
        cin >> a >> b >> m;
        int x, y;
        int d = exgcd(x,y,a,m);
        
        if(b%d) puts("impossible");
        else {
            cout << (ll)x*b/d%m << endl; // 先乘后除开ll防爆数据 
            //答案要求在int 范围，a(modm)*x(modm)=b mod(m);
        }
    }
    
    return 0;
}