ACM模版

描述

题解

典型的模线性方程组，本想着测试我的模版，后来发现我的模版只适合模数之间为互质关系才行，多少有些不合时宜。于是找了一个不断合并两个模线性方程，一直到最后变成一个方程求解的模版，作为测试使用。

测试代码

// AC 模版通过
#include <iostream>

using namespace std;

typedef long long ll;

const int MAXN = 11;

ll extgcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll d = extgcd(b, a % b, x, y);
    ll t = x;
    x = y;
    y = t - a / b * y;
    return d;
}

int n, m;
int a[MAXN], b[MAXN];

int main(int argc, const char * argv[])
{
    int T;
    cin >> T;

    while (T--)
    {
        cin >> n >> m;
        for (int i = 0; i < m; i++)
        {
            cin >> a[i];
        }
        for (int i = 0; i < m; i++)
        {
            cin >> b[i];
        }

        ll ax = a[0], bx = b[0], x, y;
        int flag = 0;
        for (int i = 1; i < m; i++)
        {
            ll d = extgcd(ax, a[i], x, y);
            if ((b[i] - bx) % d != 0)
            {
                flag = 1;   // 无整数解
                break;
            }

            ll tmp = a[i] / d;
            x = x * (b[i] - bx) / d;    // 约分
            x = (x % tmp + tmp) % tmp;
            bx = bx + ax * x;
            ax = ax * tmp;              // ax = ax * a[i] / d
        }

        if (flag == 1 || n < bx)
        {
            puts("0");
        }
        else
        {
            ll ans = (n - bx) / ax + 1;
            if (bx == 0)
            {
                ans--;
            }
            printf("%lld\n", ans);
        }
    }

    return 0;
}

测试结果

一般情况下，遇见的模数之间为非互质关系的比较多，所以我的原有的模版显得有些鸡肋，但并不是一无是处，暂且添加这更加具有一般性的模版，另一个因为暂时找不到合适的题，所以姑且审视一遍，不实测了。