X问题

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4869 Accepted Submission(s): 1617

Problem Description

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

Input

输
入数据的第一行为一个正整数T，表示有T组测试数据。每组测试数据的第一行为两个正整数N，M (0 < N <=
1000,000,000 , 0 < M <=
10)，表示X小于等于N，数组a和b中各有M个元素。接下来两行，每行各有M个正整数，分别为a和b中的元素。

Output

对应每一组输入，在独立一行中输出一个正整数，表示满足条件的X的个数。

Sample Input

3
10 3
1 2 3
0 1 2
100 7
3 4 5 6 7 8 9
1 2 3 4 5 6 7
10000 10
1 2 3 4 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8 9

Sample Output

1
0
3

1.没有整数解输出0

2.求出满足条件的最小非负整数，设该数为X

X+k*mod<=N

k<=(n-x)/mod 当X为0的时候，答案为k,如果不为0，那么将自己也算进去，答案是k+1

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <iostream>

#include <stdlib.h>

#include <math.h>

using namespace std;

typedef long long LL;

const int N = ;

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

{

    if(b==)

    {

        x=,y=;

        return a;

    }

    else

    {

        LL x1,y1;

        LL d = extend_gcd(b,a%b,x1,y1);

        x = y1;

        y = x1-a/b*y1;

        return d;

    }

}

LL m[N],a[N];///模数为m,余数为a, X % m = a

bool solve(LL &m0,LL &a0,LL m,LL a)

{

    long long y,x;

    LL g = extend_gcd(m0,m,x,y);

    LL t = a-a0>?a-a0:a0-a;

    if( t%g )return false;

    x *= (a - a0)/g;

    x %= m/g;

    a0 = (x*m0 + a0);

    m0 *= m/g;

    a0 %= m0;

    if( a0 <  )a0 += m0;

    return true;

}

/**

* 无解返回false,有解返回true;

* 解的形式最后为 a0 + m0 * t (0<=a0<m0)

*/

bool MLES(LL &m0 ,LL &a0,LL n)///解为 X = a0 + m0 * k

{

    bool flag = true;

    m0 = ;

    a0 = ;

    for(int i = ; i < n; i++)

        if( !solve(m0,a0,m[i],a[i]) )

        {

            flag = false;

            break;

        }

    return flag;

}

int main()

{

    int n;

    LL N;

    int tcase;

    scanf("%d",&tcase);

    while(tcase--)

    {

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

        for(int i=; i<n; i++)

        {

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

        }

        for(int i=; i<n; i++)

        {

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

        }

        LL m0,a0;

        bool flag = MLES(m0,a0,n);

        LL x = (a0%m0+m0)%m0;

        if(!flag) printf("0\n");

        else

        {

            if(x>N) printf("0\n");

            else{

                LL ans = (N-x)/m0;

                if(x==) printf("%lld\n",ans);

                else printf("%lld\n",ans+);

            }

        }

    }

    return ;

}

巴特西

hdu 1573(中国剩余定理)

X问题

最新文章

热门文章