题意 : 中文题不详述。
思路 : 中国剩余定理。求中国剩余定理中解的个数。看这里看这里
//
#include <stdio.h>
#include <iostream>
#include <math.h> using namespace std ; long long x,y ;
long long N,M ; long long ext_gcd(long long a,long long b)
{
long long t,d ;
if(b == )
{
x = ;
y = ;
return a;
}
d = ext_gcd(b,a%b) ;
t = x ;
x = y ;
y = t-(a/b)*y ;
return d ;
}
int main()
{
int T;
scanf("%d",&T) ;
int a[],b[] ;
int a1,b1,d,c,mod ;
while(T--)
{
scanf("%I64d %I64d",&N,&M) ;
for(int i = ; i <= M ; i++)
scanf("%d",&a[i]) ;
for(int i = ; i <= M ; i++)
scanf("%d",&b[i]) ;
a1 = a[] ;
b1 = b[] ;
int z = ;
for(int i = ; i <= M && z ; i++)
{
d = ext_gcd(a1,a[i]) ;
c = b[i]-b1 ;
if(c % d) z = ;
mod = a[i]/d ;
x = ((c/d*x)%mod+mod)%mod ;
b1 = a1*x+b1 ;
a1 = a1*mod ;
}
if(!z || b1 > N)
{
printf("0\n") ;
}
else
{
int ans = (N-b1)/a1+ ;
if(b1 == )
ans -- ;
printf("%d\n",ans) ;
}
}
return ;
}