HDU 3579——Hello Kiki

好久没写什么数论，同余之类的东西了。

昨天第一次用了剩余定理解题，今天上百度搜了一下hdu中国剩余定理。于是就发现了这个题目。

题目的意思很简单。就是告诉你n个m[i]，和n个a[i]。表示一个数对m[i]取模的值为a[i]。

乍一看以为这个题目可以用中国剩余定理，但是看仔细了吗？这里的mi并没有说是互素的哦。

肿么办？只能用安叔以前说的解同余方程的那种土方法了。

上代码：（我稍微改进了一下，根据题目的具体情况）。

#include <iostream>
#include <cstdio>
#define ll long long
#define maxn 10
using namespace std;

ll c[maxn],m[maxn],n,am,ac,y0,z0,d;
bool ans;

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

int main()
{
    ll i,t,cas=0;
    scanf("%I64d",&t);
    while (t--)
    {
        ans=true;
        scanf("%I64d",&n);
        for (i=1; i<=n; i++) scanf("%I64d",&m[i]);
        for (i=1; i<=n; i++) scanf("%I64d",&c[i]);
        am=m[1];
        ac=c[1];
        for (i=2; i<=n; i++)
        {
            exgcd(am,m[i],d,y0,z0);
            if ((ac-c[i])%d!=0)
            {
                ans=false;
                break;
            }
            y0=(c[i]-ac)/d*y0;
            y0=((y0%(m[i]/d))+(m[i]/d))%(m[i]/d);
            ac=am*y0+ac,am=am/d*m[i],ac=(ac%am+am)%am;
        }
        if (ac==0) ac=am;//这里是题目说明了整数，不能为0哦。
        printf("Case %I64d: ",++cas);
        if (ans) printf("%I64d
",ac);
            else printf("-1
");
    }
    return 0;
}