ACM模版

描述

题解

扩展 GCD+ 模线性方程。

推导如下：

n=A%MOD
n=A−AMOD∗MOD
由 AB=x ，
n=Bx−AMOD∗MOD
设 −AMOD=y ，
n=Bx+MOD∗y
故， x 即为所求。

通过扩展 GCD 最后求得：

Bx+MOD∗y=gcd(B,MOD)
由题可知， gcd(B,MOD)=1 ，所以上式最后求出的结果 x 并不是最终的结果，需要扩大 n 倍方可。

用这个题测试我的模线性方程代码并不是十分的合适，但是将就可以用。虽然线性方程不一样……

测试代码

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

using namespace std;

const int MOD = 9973;

int extgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }

    int d = extgcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - a / b * y;

    return d;
}

int modeq(int a, int b, int n)
{
    int x, y;
    extgcd(b, a, x, y);     // bx + ay = gcd(b, a) = 1
    x = (1ll * x * n % a + a) % a;

    return x;
}

int n, B;

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

    while (T--)
    {
        cin >> n >> B;

        printf("%d\n", modeq(MOD, B, n));
    }

    return 0;
}

测试结果

测试结果没有问题，虽然和模版中的线性方程有些偏颇，但是整体思想相似，故通过测试。