1
15
2016
15
2016
ACM.NEFU_84:五指山
见wy 自编的五指山题解
下面贴出本题代码
#include <cstdio>
typedef long long LL;
int T;
LL n, d, x, y, res;
inline LL gcd(const LL &a, const LL &b) {
return b == 0 ? a: gcd(b, a % b);
}
inline LL extend_gcd(const LL &a, const LL &b, LL &x, LL &y) {
if (!b) {
x = 1, y = 0;
return a;
}
else {
LL tmp;
extend_gcd(b, a % b, tmp, x);
y = tmp - x * (a / b);
}
}
int main()
{
scanf("%d", &T);
for (; T--; ) {
scanf("%lld%lld%lld%lld", &n, &d, &x, &y);
x = (y - x + n) % n;
//现在问题转化为求同余方程 d * res ≡x (mod n) 中 res 的最小非负整数解
//即求不定方程 d * res - n * par = x 的一组解
LL g = gcd(d, n), res, par;
if (x % g) {
printf("Impossible\n");
continue;
}
d /= g, n /= g, x/= g;
extend_gcd(d, n, res, par);
res %= n; if (res < 0) res += n;
res = res * x % n;
printf("%lld\n", res);
}
}
Ps:由于n达到10^9,担心出现爆int的情况， wy果断地打了long long
