Strange Way to Express Integers

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2077 字
给定若干对表示x≡a_i，求最小非负解，无解
一本通
例
正文

/*
原题：Strange Way to Express Integers (POJ 2891)
题意：给定若干对 (m_i,a_i) 表示 x ≡ a_i (mod m_i)，求最小非负解，无解输出 -1。
思路：两两合并同余式：对 x≡r (mod m) 与 x≡a (mod mi)，解 m·k ≡ a-r (mod mi)。
      用扩展欧几里得求 k，新模数取 lcm(m,mi)；若 (a-r) 不被 gcd(m,mi) 整除则无解。
复杂度：时间 O(n·log(max m_i))，空间 O(1)。
易错点：模数不一定互质，须用扩展 GCD 判可解性并取 lcm；
      多组输入读到 EOF；合并时数值可能很大，需用 __int128 累加。
*/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using i128=__int128;
i128 exgcd(i128 a, i128 b, i128 &x, i128 &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    i128 x1, y1;
    i128 g=exgcd(b, a%b, x1, y1);
    x=y1;
    y=x1-(a/b)*y1;
    return g;
}
i128 gcd(i128 a, i128 b){
    while(b){
        i128 t=a%b;
        a=b;
        b=t;
    }
    return a;
}
// 解 a*x ≡ b (mod m)，返回是否有解；有解时 x 为最小非负解（模 m/gcd）
bool lin(i128 a, i128 b, i128 m, i128 &x){
    a=((a%m)+m)%m;
    b=((b%m)+m)%m;
    i128 x0, y0;
    i128 g=exgcd(a, m, x0, y0);
    if(b%g!=0){
        return false;
    }
    i128 m1=m/g;
    x0=((x0%m1)+m1)%m1;
    x=(x0*(b/g))%m1;
    return true;
}
void print_i128(i128 x){
    if(x==0){
        cout<<0;
        return;
    }
    string s;
    while(x>0){
        s+=char('0'+(int)(x%10));
        x/=10;
    }
    reverse(s.begin(), s.end());
    cout<<s;
}
int main(){
    int n;
    while(cin>>n){
        i128 r=0, m=1;
        bool first=true;
        bool ok=true;
        for(int i=0;i<n;i++){
            ll mi_in, ai_in;
            cin>>mi_in>>ai_in;
            i128 mi=mi_in, ai=ai_in;
            if(!ok){
                continue;
            }
            if(first){
                r=((ai%mi)+mi)%mi;
                m=mi;
                first=false;
                continue;
            }
            i128 k;
            if(!lin(m, ai-r, mi, k)){
                ok=false;
                continue;
            }
            r=r+k*m;
            i128 g=gcd(m, mi);
            m=(m/g)*mi;
            r%=m;
        }
        if(!ok){
            cout<<-1<<"\n";
        }else{
            print_i128(r);
            cout<<"\n";
        }
    }
    return 0;
}
Strange Way to Express Integers

正文

一本通·提高篇的其它内容
