『算法-ACM 竞赛-数学-数论』中国剩余定理 拓展 HDU 1788

再次进行中国余数定理

问题描述
我知道部分同学最近在看中国剩余定理，就这个定理本身，还是比较简单的：
假设 m1，m2，…，mk 两两互素，则下面同余方程组：
x≡a1（mod m1）
x≡ a2（mod m2）
…
x≡ak（mod mk）
在 0 <= <m1m2 … mk 内有唯一解。
记 Mi = M / mi（1 <= i <= k），因为（Mi，mi）= 1 ，故有二个整数 pi，qi 满足 Mipi + miqi = 1，如果记 ei = Mi / pi，那么
会有：ei≡0（mod mj），j！=
iei≡1（mod mj），j = i
很容易理解，e1a1 + e2a2 + … + ekak 就是方程组的一个解，这个解加减 M 的积分倍后就可以得到最小的非负积分解。
这就是中国剩余定理及其取代过程。
现在有一个问题是这样的：
一个正整数 N 除以 M1 余（M1-a），除以 M2 余（M2-a），除以 M3 余（M3-a），总之，除以 MI 余（MI-a），其中（a <Mi <100 i = 1,2，…I），求满足条件的最小的数。

输入项
输入数据包含多组测试实例，每个实例的第一行是两个整数 I（1 <I <10）和 a，其中，I 表示 M 的个数，a 的表示替代，紧接着的一行是 I 个整数 M1，M1 … MI，I = 0 并且 a = 0 结束输入，不处理。

输出量
对于每个测试实例，请在一行内部输出满足条件的最小的数。每个实例的输出占一行。

样本输入
2 1
2 3
0 0

样本输出
5
不能满足沪指的方程组，ExCrt 完事

#include<iostream>
using namespace std;
#define LL long long
LL mi[1100],ai[1100];//mi为要模的数,ai为余数。
LL gcd(LL a, LL b)
{
    return b == 0 ? a : gcd(b, a%b);
}
void exgcd(LL a, LL b, LL &d, LL &x, LL &y)
{
    if(!b)
    {
        d = a, x = 1, y = 0;
    }
    else
    {
        exgcd(b, a%b, d, y, x);
        y -= x * (a / b);
    }
}
LL CRT(LL l, LL r, LL *mi, LL *ai)
{
    LL lcm = 1;
    for(LL i = l; i <= r; i++)
        lcm = lcm / gcd(lcm, mi[i]) * mi[i];
    for(LL i = l+1; i <= r; i++)
    {
        LL A = mi[l], B = mi[i], d, x, y, c = ai[i] - ai[l];
        exgcd(A, B, d, x, y);
        if(c % d)
            return -1;
        LL mod = mi[i] / d;
        LL k = ((x * c / d) % mod + mod) % mod;
        ai[l] = mi[l] * k + ai[l];
        mi[l] = mi[l] * mi[i] / d;
    }
    /*if(ai[l] == 0)
        return lcm;*/ //保证结果为正整数
    return ai[l];
}
int main()
{
    LL t,n,i,aa;
    while(cin>>n>>aa)
    {
		if(n==0) break;
        for(i=1; i<=n; i++){
            cin>>mi[i];
			ai[i]=mi[i]-aa;
		}
        cout<<CRT(1ll,n,mi,ai)<<endl;
    }
    return 0;
}