青蛙的约会
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