题目链接：

http://acm.hdu.edu.cn/showproblem.php?

pid=1573

题目大意：

求在小于等于N的正整数中有多少个X满足：X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2],

…, X mod a[i] = b[i], … (0 < a[i] <= 10)。

思路：

先求出数组b[]中全部数的最小公倍数lcm，再求解出该一元线性同余方程组在lcm范围内的解为a。题目要

求解x是小于等于N的正整数，则可列不等式：a + lcm * x <= N。

那么，假设a = 0，则答案为x-1。假设

a != 0，则答案为x。

AC代码：

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

using namespace std;

__int64 GCD(__int64 a,__int64 b)

{

    if(b == 0)

        return a;

    else

        return GCD(b,a%b);

}

void ExGCD(__int64 a,__int64 b,__int64 &d,__int64 &x,__int64 &y)

{

    if( !b )

    {

        x = 1;

        y = 0;

        d = a;

    }

    else

    {

        ExGCD(b,a%b,d,y,x);

        y -= x * (a/b);

    }

}

__int64 A[15],B[15];

int main()

{

    int T,N,M;

    __int64 a,b,c,d,x0,y0,lcm;

    cin >> T;

    while(T--)

    {

        cin >> N >> M;

        bool flag = 1;

        lcm = 1;

        for(int i = 1; i <= M; ++i)

        {

            cin >> A[i];

            lcm = lcm / GCD(lcm,A[i]) * A[i];

        }

        for(int i = 1; i <= M; ++i)

            cin >> B[i];

        for(int i = 2; i <= M; ++i)

        {

            a = A[1];

            b = A[i];

            c = B[i] - B[1];

            ExGCD(a,b,d,x0,y0);

            if(c % d != 0)

            {

                flag = 0;

                break;

            }

            __int64 temp = b / d;

            x0 = (x0*(c/d)%temp + temp) % temp;

            B[1] = A[1] * x0 + B[1];

            A[1] = A[1] * (A[i]/d);

        }

        if( !flag )

        {

            cout << "0" << endl;

            continue;

        }

        __int64 Ans = 0;

        if(B[1] <= N)

            Ans = 1 + (N - B[1])/lcm;

        if(Ans && B[1] == 0)

            Ans--;

        cout << Ans << endl;

    }

    return 0;

}