【POJ2891】Strange Way to Express Integers

佚名 6年前 (2019-04-18) 随笔 1882人围观抢沙发百度已收录

题目大意：给定 M 组线性同余方程，要求将这 M 个同余方程合并成一个，并输出最小正整数解。

题解：学会了扩展中国剩余定理。
题目细节很多，需要对扩展欧几里得算法的通解理解透彻才能解决这个问题。QAQ

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

根据数学归纳法，假设现在已经合并了前 \(k-1\) 个同余方程，现要合并第 \(k\) 个方程。
\[x+m*t \equiv a_i \mod b_i\]
\[t*m \equiv a_i-x \mod b_i\]
根据扩展欧几里得算法可以求出系数 \(t\)，再根据 \(t\) 进行合并即可。

注意：

洛谷的模板中需要用到乘法取模操作，在乘法取模时，若移位的是负数，会导致死循环，原因是移位的过程中，负数移位是算术移位，最高位补 1，就会导致死循环，因此需要将可能出现负数的地方变成正数。
在系数调整的时候，需要进行取模操作，否则会爆 long long。

代码如下

#include <cstdio>
using namespace std;
typedef long long ll;

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

ll n,ans,lcm,m,a,s,t;

void excrt(){
    int flag=0;
    scanf("%lld%lld",&lcm,&ans);
    while(--n){
        scanf("%lld%lld",&m,&a);
        ll c=((a-ans)%m+m)%m;
        ll d=exgcd(lcm,m,s,t);
        if(c%d)flag=1;
        s=c/d*s%(m/d);// trap: overflow 
        ans+=s*lcm,lcm=m/d*lcm,ans=(ans%lcm+lcm)%lcm;
    }
    if(flag)puts("-1");
    else printf("%lld\n",ans);
}

int main(){
    while(scanf("%lld",&n)!=EOF)excrt();
    return 0;
}