同余方程模板

同余方程模板:

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

求关于 x 的同余方程ax≡1(modb)的最小正整数解，若无解，输出"-1"。

输入描述:

第一行一个正整数 T，表示 T组数据。
接下来 T行，每行两个正整数  a,b(2≤a,b≤2*10^9) 。

输出描述:

对于每组数据，输出同余方程的最小正整数解，若无解，输出"-1"（没有引号）。

示例1

输入

2 3 10 2 4

2
3 10
2 4

输出

7 -1

7
-1

AC代码:

#include 
using namespace std;
long long exgcd(long long a,long long b,long long &x,long long &y){
    if(!b){
        x = 1;
        y = 0;
        return a；
    }
    long long d = exgcd(b,a % b,x , y);
    long long z = x;
    x = y;
    y = z - y * (a / b);
    return d;
}
void solve(){
    long long a,b;
    cin >> a >> b;
    long long x ,y;
    long long d = exgcd(a,b,x,y);
    if(d != 1){
        cout << "-1" << endl;
    }
    else{
        x = (x % b + b) % b;
        cout << x << endl;
    }
    return ;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}

同余方程模板:

long long exgcd(long long a,long long b,long long &x,long long &y){
    if(!b){
        x = 1;
        y = 0;
        return a;
        
    }
    long long d = exgcd(b,a % b,x , y);
    long long z = x;
    x = y;
    y = z - y * (a / b);
    return d;
}
void solve(){
    long long a,b;
    cin >> a >> b;
    long long x ,y;
    long long d = exgcd(a,b,x,y);
    if(d != 1){
        cout << "-1" << endl;
    }
    else{
        x = (x % b + b) % b;
        cout << x << endl;
    }
    return ;
}

ax≡1(modb)时间复杂度O(log(a+b));