Luogu P3421[POI2005]SKO-Knights

发表于 | 阅读次数：

因为LATEX挂了，所以重新交一遍

分析

我们设原向量为$(a_1, b_1)$,$(a_2, b_2)$。
设新向量为$(a_3, b_3)$，$(0, a_4)$

$\therefore$ $a_3=gcd(a_1,a_2)$

$\therefore$ $a_1x + a_2y = a_3$

$\therefore$ $a_1x + a_2y = gcd(a_1,a_2)$ $b_1x + b_2y = b_3$

$\begin{cases}a_1x + a_2y = 0\b_1x + b_2y = b_4\end{cases}$

$\therefore$ $-y = \dfrac{a_1x}{a_2}$

$\because$ $-y$是整数

$\therefore$ $a_2|a_1x$

即$\dfrac{a_2}{gcd(a_1,a_2)}|\dfrac{a_1}{gcd(a_1,a_2)x}$

又$\therefore$ $\dfrac{a_2}{gcd(a_1,a_2)}|\dfrac{a_1}{gcd(a_1,a_2)x}$互质

$\therefore$ $\dfrac{a_2}{gcd(a_1,a_2)}|x$

设$x=\dfrac{a_2}{gcd(a_1,a_2)}$

$\therefore$ $-\dfrac{a_1}{gcd(a_1,a_2)}$

$\therefore$ $b_4 = \dfrac{|b_1a_2-b_2a_1|}{gcd(a_1,a_2)}$

我们只需要不断的将向量转变到y轴上使得最终至多一个向量不再y轴上就行了。

代码:

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>
int a[510], b[510];
template<class type>type _gcd(type __, type ___) {
	return (!___) ? __ : _gcd(___, __ % ___);
}
template<class type>type _abs(type __) {
	return __ < 0 ? -__ : __;
}
inline void exgcd(int a, int b, int &x, int &y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return;
	}
	exgcd(b, a%b, x, y);
	int z = x;
	x = y;
	y = z - (a / b)*y;
}
int main() {
	int n, m, x, y;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d%d", &a[i], &b[i]);
	int a1, b1, a2, b2;
	if (!a[1]) { a1 = a[2]; b1 = b[2]; b2 = b[1]; }
	else if (!a[2]) { a1 = a[1]; b1 = b[1]; b2 = b[2]; }
	else { a1 = _gcd(a[1], a[2]); exgcd(a[1] / a1, a[2] / a1, x, y); b1 = b[1] * x + b[2] * y; b2 = _abs(b[1] * a[2] - b[2] * a[1]) / a1; }
	for (int i = 3; i <= n; i++) {
		if (!a1) { a1 = a[i]; b2 = _gcd(b2, b1); b1 = b[i]; }
		else if (!a[i])b2 = _gcd(b2, b[i]);
		else { int be = a1, be2 = b1; a1 = _gcd(a1, a[i]); exgcd(be / a1, a[i] / a1, x, y); b1 = b1 * x + b[i] * y; b2 = _gcd(b2, _abs(be2*a[i] - b[i] * be) / a1); }
	}
	printf("%d %d\n", a1, b1);
	putchar('0'), putchar(' ');
	printf("%d\n", b2);
	return 0;
}

码风较丑，见谅