Hdu 1573(扩展中国剩余定理)

Hdu 1573
题意：求同余方程组小于某数的解的个数。

利用中国剩余定理求出最小一个整数解，因为模数不互质，要一一合并。
由于解有周期性，用最大限度值减去最小解除以周期即为答案，但是要记住正整数解不包括0，所以如果最小解为0要舍弃。即如果最小解不在$(0, n]$范围内则整个同余方程组无解。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#defin#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
LL n, m, mi[20], ai[20];
LL gcd(LL a, LL b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
LL lcm(LL a, LL b) {return a * b / gcd(a, b);}
void exgcd(LL a, LL b, LL &x, LL &y) {
    if (b == 0) {
        x = 1, y = 0;
        return ;
    }
    exgcd(b, a % b, x, y);
    LL tmp = x;
    x = y, y = tmp - a / b * y;
}
void clean() {}
int solve() {
    scanf("%lld%lld", &n, &m);
    clean();
    for (LL i = 1; i <= m; i++) scanf("%lld", &mi[i]);
    for (LL i = 1; i <= m; i++) scanf("%lld", &ai[i]);
    for (LL i = 2; i <= m; i++) {
        LL x1, x2, a = mi[i - 1], b = mi[i], c = ai[i] - ai[i - 1];
        LL g = gcd(a, b);
        if (c % g != 0) {
            return printf("0\n"), 0;
        }
        a /= g, b /= g, c /= g;
        exgcd(a, b, x1, x2);
        b = (b > 0) ? b : -b;
        x1 = (x1 * c % b + b) % b;
        ai[i] = ai[i - 1] + mi[i - 1] * x1;
        mi[i] = lcm(mi[i], mi[i - 1]);
    }
    LL x1, x2, a = 1, b = -mi[m], c = ai[m];
    LL g = gcd(a, b);
    if (c % g != 0) {
        return printf("0\n"), 0;
    }
    a /= g, b /= g, c /= g;
    exgcd(a, b, x1, x2);
    b = (b > 0) ? b : -b;
    x1 = (x1 * c % b + b) % b;
    LL ans = (n - x1) / b;
    if (x1 != 0 && x1 <= n) ans++;
    printf("%lld\n", ans);
    return 0;
}
int main() {
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}