http://acm.hdu.edu.cn/showproblem.php?pid=1573
X问题
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4439 Accepted Submission(s): 1435
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
3
这道题除数不是两两互质的，也就不能直接套用中国剩余定理模板，既然不能直接套用就两两合成
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<stdlib.h> using namespace std; const int M = ;
typedef long long ll;
int r;
ll n[M], b[M], N; void gcd(ll a, ll b, ll &x, ll &y)
{
if(b == )
{
x = ;
y = ;
r = a;
return ;
}
gcd(b, a % b, x, y);
ll t = x;
x = y;
y = t - a / b * y;
}
ll CRT2(ll b[], ll n[], int m)
{
int f = ;
ll n1 = n[], n2, b1 = b[], b2, c, t, k, x, y;
for(int i = ; i < m ; i++)
{
n2 = n[i];
b2 = b[i];
c = b2 - b1;
gcd(n1, n2, x, y);
if(c % r != )
{
f = ;
break;
}
k = c / r * x;
t = n2 / r;
k = (k % t + t) % t;
b1 = b1 + n1 * k;
n1 = n1 * t;
}
if(f)//无解
return ;
if(b1 == )
b1 = n1;
if(b1 > N)
return ;
return (N - b1) / n1 + ;
} int main()
{
int t, m;
scanf("%d", &t);
while(t--)
{
scanf("%lld%d", &N, &m);
for(int i = ; i < m ; i++)
scanf("%lld", &n[i]);
for(int i = ; i < m ; i++)
scanf("%lld", &b[i]);
printf("%lld\n", CRT2(b, n, m));
}
return ;
}