1
17
2016
0

POJ1061 -- 青蛙的约会

青蛙的约会

Category: POJ | Tags: POJ 数论 拓展欧几里得
1
15
2016
0

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

Category: Others | Tags: 数论 拓展欧几里得

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com