首页 > 代码库 > 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(数论+推理)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。