链接：

题意：

求在小于等于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)。

思路：

解线性同余方程组，得到\(x+k*m \leq n\)。

解为\(1+(n-x)/m\)。

当x为0时答案要减一。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<math.h>

#include<vector>

using namespace std;

typedef long long LL;

const int INF = 1e9;

const int MAXN = 1e6+10;

LL a, b, c, k, n, lcm;

int m;

LL M[20], A[20];

LL ExGcd(LL a, LL b, LL &x, LL &y)

{

    if (b == 0)

    {

        x = 1, y = 0;

        return a;

    }

    LL d = ExGcd(b, a%b, x, y);

    LL tmp = x;

    x = y;

    y = tmp - (a/b)*y;

    return d;

}

LL ExCRT()

{

    LL res = A[1], mod = M[1];

    LL x, y, gcd;

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

    {

        gcd = ExGcd(mod, M[i], x, y);

        if ((A[i]-res)%gcd)

            return -1;

        x = (x*(A[i]-res))/gcd;

        x = (x%(M[i]/gcd)+(M[i]/gcd))%(M[i]/gcd);

        res = res+mod*x;

        mod = (mod*M[i])/gcd;

        res %= mod;

    }

    lcm = mod;

    return res;

}

int main()

{

    int t;

    scanf("%d", &t);

    while(t--)

    {

        scanf("%lld%d", &n, &m);

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

            scanf("%lld", &M[i]);

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

            scanf("%lld", &A[i]);

        LL res = ExCRT();

        if (res == -1 || res > n)

            puts("0");

        else

        {

            printf("%lld\n", (n-res)/lcm+(res!=0));

        }

    }

    return 0;

}

巴特西

HDU-1573-X问题（线性同余方程组）

链接：

题意：

思路：

代码：

最新文章

热门文章