首页 > 代码库 > UVA 11024 - Circular Lock(数论+推理)

UVA 11024 - Circular Lock(数论+推理)

UVA 11024 - Circular Lock

题目链接

题意:给定一个矩阵,每次能在一行或者一列都加1,问能否构造出满足每个位置%P都等于0的矩阵,P的得到方法为矩阵p所有数字的gcd

思路:推公式啊,一共4个加值的方法,分别为A,B,C,D
A + C 加到A位置上a + k1 p,a为原位置差多少为p的倍数
同理
A + D 加到A位置上b + k2
p
B + C 加到A位置上c + k3 p
B + D 加到A位置上d + k4
p
这样一来消掉就得到a - b - c + d + (k1 - k2 - k3 + k4) * p = 0;

因此只要判断a - b - c + d是否是p的倍数,如果是就必然能构造出

代码:

#include <cstdio>
#include <cstring>

int t, s[2][2], p[2][2];

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

int main() {
	scanf("%d", &t);
	while (t--) {
		for (int k = 0; k < 2; k++) {
			for (int i = 0; i < 2; i++)
				scanf("%d", &s[k][i]);
			for (int i = 0; i < 2; i++)
				scanf("%d", &p[k][i]);
		}
		int P = p[0][0];
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++)
				P = gcd(P, p[i][j]);
		int sum = 0;
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++) {
				if (i == j) sum -= P - s[i][j];
				else sum += P - s[i][j];
			}
		}
		printf("%s\n", sum % P == 0 ? "Yes" : "No");
	}
	return 0;
}


UVA 11024 - Circular Lock(数论+推理)