题意 ： 中文题不详述。
思路 ： 中国剩余定理。求中国剩余定理中解的个数。看这里看这里
1 //1573 2 #include <stdio.h> 3 #include <iostream> 4 #include <math.h> 5 6 using namespace std ; 7 8 long long x,y ; 9 long long N,M ; 10 11 long long ext_gcd(long long a,long long b) 12 { 13 long long t,d ; 14 if(b == 0) 15 { 16 x = 1 ; 17 y = 0 ; 18 return a; 19 } 20 d = ext_gcd(b,a%b) ; 21 t = x ; 22 x = y ; 23 y = t-(a/b)*y ; 24 return d ; 25 } 26 int main() 27 { 28 int T; 29 scanf("%d",&T) ; 30 int a[110],b[110] ; 31 int a1,b1,d,c,mod ; 32 while(T--) 33 { 34 scanf("%I64d %I64d",&N,&M) ; 35 for(int i = 1 ; i <= M ; i++) 36 scanf("%d",&a[i]) ; 37 for(int i = 1 ; i <= M ; i++) 38 scanf("%d",&b[i]) ; 39 a1 = a[1] ; 40 b1 = b[1] ; 41 int z = 1 ; 42 for(int i = 2 ; i <= M && z ; i++) 43 { 44 d = ext_gcd(a1,a[i]) ; 45 c = b[i]-b1 ; 46 if(c % d) z = 0 ; 47 mod = a[i]/d ; 48 x = ((c/d*x)%mod+mod)%mod ; 49 b1 = a1*x+b1 ; 50 a1 = a1*mod ; 51 } 52 if(!z || b1 > N) 53 { 54 printf("0 ") ; 55 } 56 else 57 { 58 int ans = (N-b1)/a1+1 ; 59 if(b1 == 0) 60 ans -- ; 61 printf("%d ",ans) ; 62 } 63 } 64 return 0 ; 65 }