HDU-1576-A/B

2019-04-13 20:41发布

站内文章 / 模拟电子
14938 0 1682
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 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 ", modeq(MOD, B, n)); } return 0; }

测试结果

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

热门文章