扩展 GCD+ 模线性方程。
推导如下:n=A%MODn=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 usingnamespacestd;
constint 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, constchar * argv[])
{
int T;
cin >> T;
while (T--)
{
cin >> n >> B;
printf("%d
", modeq(MOD, B, n));
}
return0;
}