【HDU1573】X问题

【题目描述】

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

【题解】

模板题，为读者提供一个中国剩余定理（非互质版）的模板

 1 /*************
 2   HDU 1573
 3   by chty
 4   2016.11.2
 5 *************/
 6 #include<iostream>
 7 #include<cstdio>
 8 #include<cstdlib>
 9 #include<cstring>
10 #include<cmath>
11 #include<ctime>
12 #include<algorithm>
13 using namespace std;
14 int T,n,s,M,ans,flag,a[15],m[15];
15 inline int read()
16 {
17     int x=0,f=1;  char ch=getchar();
18     while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
19     while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
20     return x*f;
21 }
22 void exgcd(int a,int b,int &g,int &x,int &y)
23 {
24     if(b==0)  {x=1; y=0; g=a; return;}
25     exgcd(b,a%b,g,x,y);
26     int t=x;x=y;y=t-a/b*y;
27 }
28 void China()
29 {
30     int A=a[1],k,y;  M=m[1];
31     for(int i=2;i<=n;i++)
32     {
33         int da=a[i]-A,g;
34         exgcd(M,m[i],g,k,y);
35         if(da%g)  {flag=1; return;}
36         int t=m[i]/g;
37         k*=da/g;
38         k=(k+t)%t;
39         A+=k*M;
40         M=M*m[i]/g;
41         A=(A+M)%M;
42     }
43     ans=A;
44 }
45 int main()
46 {
47     freopen("cin.in","r",stdin);
48     freopen("cout.out","w",stdout);
49     T=read();
50     while(T--)
51     {
52         s=read();  n=read();  flag=0;
53         for(int i=1;i<=n;i++)  m[i]=read();
54         for(int i=1;i<=n;i++)  a[i]=read();
55         China();
56         if(ans>s||flag)  {printf("0
");  continue;}
57         int sum=(s-ans)/M+1;
58         if(ans==0)  sum--;
59         printf("%d
",sum);
60     }
61     return 0;
62 }