X问题

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

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

Author

lwg

Source

HDU 2007-1 Programming Contest

题解：

这个题直接给出了中国剩余定理的形式：X===a[i](mod b[i])但是这里注意一下这个b[i]之间有可能不是互素的，所以这里给出一个不互素的中国剩余定理的求解方式

考虑两个方程

x===a1(mod b1)

x===a2(mod b2)

可得：x = a1+b1*r1;

　　　x = a2+b2*r2;

有 a1+b1*r1 = a2+b2*r2;

有b1*r1-b2*r2 = a2-a1

这样可以通过扩展欧几里得解的r1，这里注意一下(a2-a1)%gcd(b1,b2)==0时候有解

解出r1后则x0 = a1+b1*r1位这个方程组的一个解

则这两个方程可以写成是x===x0(mod b1*b2/gcd(b1,b2))的形式

然后依次处理没两个式子，最后得到的就是解

注意这里每次求得的解都要保证是最小的解的形式，所以可以通过用(x%mod+mod)%mod 的形式来控制

最后统计次数的时候从最小的时候循环到n即可统计出个数

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define ll long long
 6 ll a[15],b[15];
 7 ll exgcd(ll a, ll b, int &x, int &y)
 8 {
 9     if(b==0){
10         x = 1;
11         y = 0;
12         return a;
13     }
14     ll ans = exgcd(b,a%b,x,y);
15     int tx = x;
16     x = y;
17     y = tx-(a/b)*y;
18     return ans;
19 }
20 
21 int main()
22 {
23     int T;
24     scanf("%d",&T);
25     while(T--)
26     {
27         ll n,m;
28         scanf("%lld%lld",&n,&m);
29         for(int i = 0; i < m; i++){
30             scanf("%lld",&a[i]);
31         }
32         for(int i = 0; i < m; i++){
33             scanf("%lld",&b[i]);
34         }
35         bool fl = 0;
36         for(int i = 1; i < m; i++){
37             //更新a[i]和b[i];
38             int x, y;
39             ll d = exgcd(a[i-1],a[i],x,y);
40             if((b[i]-b[i-1])%d){
41                 fl = true;
42                 break;
43             }
44             ll t = a[i]/d;
45             x = x*(b[i]-b[i-1])/d;
46             x = (x%t+t)%t;
47             ll N = a[i-1]*x+b[i-1];
48             b[i] = N;
49             a[i] = a[i]*a[i-1]/d;
50             b[i] = (b[i]%a[i]+a[i])%a[i];
51         }
52         if(fl||n<b[m-1]) printf("0
");
53         else printf("%d
",(n-b[m-1])/a[m-1]+1-(b[m-1]==0?1:0));//因为要求是正整数，所以0不可以取
54     }
55     return 0;
56 }