X问题

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

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
3
2 3
1 2
7
4 5 6 7 8 9
2 3 4 5 6 7
10
2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9

Sample Output

1
0
3

Author

lwg

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

/*对于x=r0(mod m0)
     x=r1(mod m1)
        ...
     x=rn(mod mn)
输入数组m和数组r，返回[0,[m0,m1,...,mn]-1] 范围内满足以上等式的x0。
x的所有解为:x0+z*[m0,m1,...mn](z为整数)
*/
long long cal_axb(long long a,long long b,long long mod)
{
    //防乘法溢出
    long long sum=0;
    while(b)
    {
        if(b&1) sum=(sum+a)%mod;
        b>>=1;
        a=(a+a)%mod;
    }
    return sum;
}

//ax + by = gcd(a,b)
//传入固定值a,b.放回 d=gcd(a,b), x , y
void extendgcd(long long a,long long b,long long &d,long long &x,long long &y)
{
    if(b==0){d=a;x=1;y=0;return;}
    extendgcd(b,a%b,d,y,x);
    y -= x*(a/b);
}

long long Multi_ModX(long long m[],long long r[],int n,long long &M)
{
    long long m0,r0;
    m0=m[0]; r0=r[0];
    for(int i=1;i<n;i++)
    {
        long long m1=m[i],r1=r[i];
        long long k0,k1;
        long long tmpd;
        extendgcd(m0,m1,tmpd,k0,k1);
        if( (r1 - r0)%tmpd!=0 ) return -1;
        k0 *= (r1-r0)/tmpd;
        m1 *= m0/tmpd;
        r0 = ( cal_axb(k0,m0,m1)+r0)%m1;
        m0=m1;
    }
    M=m0;
    return (r0%m0+m0)%m0;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        long long n,m;
        cin>>n>>m;
        long long a[110],b[110];
        for(int i=0;i<m;i++)
            cin>>a[i];
        for(int i=0;i<m;i++)
            cin>>b[i];
        long long M;
        long long ans = Multi_ModX(a,b,m,M);
        if(ans==-1)
        {
            printf("0
");
        }
        else
        {
            //从[1,N],有多少个
            if( ans==0 )
            {
                cout<<n/M<<endl;
            }
            else
            {
                long long tans=n/M;
                if( n%M >= ans ) tans++;
                cout<<tans<<endl;
            }
        }
    }
    return 0;
}