青蛙的约会
1
15
2016
15
2016
ACM.NEFU_84:五指山
见wy 自编的五指山题解
下面贴出本题代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | #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
