题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1573

题解:

对互质的情况,处理起来比较方便,可以直接套模板。

本题给出不互质的模线性方程组,求出满足方程的最小正整数解方案:

对于不互质的模线性方程组,可以进行方程组合并,求出合并后的方程的解,这样就可以很快地推出方程的最终解。

两个方程合并的一种方法:

x = c1 (mod b1)

x = c2 (mod b2)

此时b1,b2不必互质的。

显然可以得到

x = k1 * b1 + c1

x = k2 * b2 + c2

两个方程合并一下就可以得到:

k1 * b1 = c2 - c1 (mod b2)

这样可以设 g=gcd(b1,b2)

于是就有 b1/g*k1-b2/g*k2=(c2-c1)/g

显然判断(c2-c1)/g是否为整数就能判断是否存在解。

这样在经过类似的变换就能得到 k1 = K (mod (b2/g))

最后得到 x = K*b1 + c1 (mod (b1 * b2/g))。

对于题目所给正整数的要求,只有一种反例,就是结果输出为0的情况,这个可以特殊考虑,只需要考虑所有数的最小公倍数即可。

/*
 * Author: Haipz
 * School: HDU
 * File Name: 1001.cpp
 */
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cctype>
#include <cfloat>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

long long gcd(long long a, long long b) {
    if (b) return gcd(b, a % b);
    return a;
}

long long ex_gcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int d = ex_gcd(b, a % b, y, x);
    y -= a/b*x;
    return d;
}

long long inv(long long a, long long n) {
    long long x, y;
    long long t = ex_gcd(a, n, x, y);
    if (t != 1) return -1;
    return (x % n + n ) % n;
}

bool merge(long long n1, long long a1, long long n2, long long a2, long long &n3, long long &a3) {
    long long d = gcd(n1, n2), c = a2 - a1;
    if (c % d) return false;
    c = (c % n2 + n2) % n2;
    c /= d, n1 /= d, n2 /= d;
    c *= inv(n1, n2);
    c %= n2, c *= n1*d, c += a1;
    n3 = n1*n2*d, a3 = (c % n3 + n3) % n3;
    return true;
}

long long CRT(long long *n, long long *a, int len, long long &lcm) {
    long long n1 = n[0], a1 = a[0];
    for (int i = 1; i < len; ++i) {
        long long n2 = n[i], a2 = a[i], aa, nn;
        if (!merge(n1, a1, n2, a2, nn, aa)) return -1;
        a1 = aa, n1 = nn;
    }
    lcm = n1;
    return (a1 % n1 + n1) % n1;
}

const int N = 1000000000, M = 10;
long long a[M + 5], w[M + 5];

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        long long n;
        int m;
        scanf("%I64d%d", &n, &m);
        for (int i = 0; i < m; ++i) scanf("%I64d", &a[i]);
        for (int i = 0; i < m; ++i) scanf("%I64d", &w[i]);
        long long lcm;
        long long d = CRT(a, w, m, lcm);
        if (d == -1 || n < d) printf("0\n");
        else printf("%I64d\n", (n - d)/lcm + 1 - (d == 0 ? 1 : 0));
    }
    return 0;
}

转载保留版权:http://haipz.com/blog/i/5548 - 海胖博客