[编程题]小红走网格
- 热度指数：3399 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 1024M，其他语言2048M
- 算法知识视频讲解
输入描述:
每个测试文件均包含多组测试数据。第一行输入一个整数
代表数据组数，每组测试数据描述如下：
代表目标位置所在坐标、向上下左右四个方向单次移动的步数。
输出描述:
；否则，直接输出
。
示例1
输入
3 1 1 1 1 1 1 3 3 6 6 6 6 5 1 1 1 1 3
输出
YES NO YES
说明
步到达
，然后向右移动
。
。
步到达
、向左移动
、向右移动
、最后向上移动
。
数论的内容。。。求的就是： am + bn = y 有没有整数的m、n 使得等式成立。有解的条件是 gcd(a, b) 能整除 y。
简单证明一下 为什么 gcd(a, b) 能被 a 和 b的线性组合 y 整除
因为 gcd(a, b) 能整除 a， 也能整除 b。所以 a = k * gcd(a, b)，b = o * gcd(a, b)
代入 am + bn = k * gcd(a, b) + o * gcd(a, b) = gcd(a, b) * (k + o)
得到 (am + bn ) / gcd(a, b) = (k + o)
因为 k 和 o 都是整数，所以 gcd(a, b) 能被 a 和 b 的线性组合 整除
发表于 2025-05-17 13:40:22
回复(0)
//只要分析得出来 输出yes和no需要满足条件 就很容易 输出YES需要满足 x % （c,d的公共公因数）== 0 且 y % （a,b的公共公因数）== 0 需要用到数学贝祖定理 方法
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
in.nextLine();
while (T-- > 0) {
int x = in.nextInt();
int y = in.nextInt();
int a = in.nextInt();
int b = in.nextInt();
int c = in.nextInt();
int d = in.nextInt();
if (x % gcd(c, d) == 0 && y % gcd(a, b) == 0) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
private static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
发表于 2025-03-19 14:56:05
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int T = scanner.nextInt();
while (T-- > 0) {
long x = scanner.nextLong();
long y = scanner.nextLong();
long a = scanner.nextLong();
long b = scanner.nextLong();
long c = scanner.nextLong();
long d = scanner.nextLong();
// 计算y方向所需的最大公约数
long gcdY = gcd(a, b);
// 计算x方向所需的最大公约数
long gcdX = gcd(c, d);
// 判断y是否是gcd(a,b)的倍数，且x是否是gcd(c,d)的倍数
if (y % gcdY == 0 && x % gcdX == 0) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
scanner.close();
}
// 欧几里得算法计算最大公约数
private static long gcd(long a, long b) {
while (b != 0) {
long temp = b;
b = a % b;
a = temp;
}
return a;
}
}
发表于 2025-09-07 16:54:14
回复(0)
def gcd(a ,b):
while b:
a, b = b, a % b
return a
import sys
line = sys.stdin.read().splitlines()
for l in line[1: ]:
x, y, a, b, c, d = (int(i) for i in l.split(' '))
if (not x % gcd(c, d)) and (not y % gcd(a, b)):
print('YES')
else:
print('NO')
对于整数x，y，i，若存在整数a，b使ax+by=i，则i %gcd（x，y）=0，若x=y=0则显然i=0
发表于 2025-08-02 00:05:50
回复(0)
看懂规律后实际上是比较简单的题，求最大公约数gcd的题，
我们可以无数次根据规定步数向上下左右走，竖直方向所能到达的地方是单次往上下方向走的最大公约数的倍数，
左右方向所能到达的地方是左右的最大公约数的倍数。
比如3和5，最大公约数是1，任何方向都能到达。2和8，最大公约数是2，任何2的倍数位置都能到达，比如-4 -2 0 2 4.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int T = in.nextInt();
for (int i = 0; i < T; i++) {
int leftRight = in.nextInt();
int upDown = in.nextInt();
int up = in.nextInt();
int down = in.nextInt();
int left = in.nextInt();
int right = in.nextInt();
int shangXia = gcd(Math.abs(up), Math.abs(down));
int zuoYou = gcd(Math.abs(left), Math.abs(right));
if ((upDown % shangXia == 0) && (leftRight % zuoYou == 0)) {
System.out.println("YES");
} else System.out.println("NO");
}
}
}
private static int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
}
发表于 2025-07-26 01:00:35
回复(0)
判断a，b能否线性组合成x,根据裴蜀定理（Bézout's Identity）
令gcd(a,b)=d，则：
x 可以表示成 a 和 b 的整数线性组合的充要条件是：d%x==0
也就是说，只要 x 是 a 和 b 的最大公约数的倍数，就能线性组合成 x。
发表于 2025-07-17 09:36:26
回复(0)
简洁清晰
#include <stdio.h>
#include <stdlib.h>
int gcd(int a,int b){
if(b == 0) return a;
return gcd(b,a%b);
}
int main() {
int n;
scanf("%d",&n);
int x,y,up_step,down_step,left_step,right_step;
for(int i = 0;i < n;i++){
scanf("%d%d%d%d%d%d",&x,&y,&up_step,&down_step,&left_step,&right_step);
if(abs(x) % gcd(left_step,right_step) == 0 && abs(y) % gcd(up_step,down_step) == 0){
printf("YES\n");
}
else{
printf("NO\n");
}
}
return 0;
}
发表于 2025-06-05 14:45:21
回复(0)
package main
import (
"fmt"
)
func main() {
var T int
fmt.Scan(&T)
results := make([]string, T)
for i := 0; i < T; i++ {
nums := make([]int, 6)
for j := 0; j < 6; j++ {
fmt.Scan(&nums[j])
}
x := nums[0]
y := nums[1]
g_x := gcd(nums[4], nums[5])
g_y := gcd(nums[2], nums[3])
if x%g_x == 0 && y%g_y == 0 {
results[i] = "YES"
} else {
results[i] = "NO"
}
}
for _, v := range results {
fmt.Println(v)
}
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}
发表于 2025-05-19 14:09:53
回复(0)
n = input()
def is_t(a, b, x):
for i in range(10):
for j in range(10):
res = i * a + j * b
if res == x:
return True
return False
while True:
try:
x,y,a,b,c,d = map(int,input().split())
b = -b
c = -c
if is_t(a,b,x) and is_t(c,d,y):
print('YES')
else:
print('NO')
except:
break
不够完善
不够完善
发表于 2025-04-20 13:36:42
回复(2)
Java转C++代码太香了，讨论区都是大佬，拜一拜
#include <iostream>
using namespace std;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int main() {
int T;
cin >> T;
while (T-- > 0) {
int x, y, a, b, c, d;
cin >> x >> y >> a >> b >> c >> d;
if (x % gcd(c, d) == 0 && y % gcd(a, b) == 0) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
return 0;
}
发表于 2025-04-09 15:20:49
回复(0)
最多只能走到a,b的最大公约数的倍数，原先手搓的暴力算gcd超时了，换成了辗转相除法
def gcd(a, b):
while b:
a, b = b, a % b
return a
def solve():
x, y, a, b, c, d = map(int, input().split())
g_x = gcd(c, d) # 最多只能走到c, d最大公约数的倍数
g_y = gcd(a, b)
if x % g_x == 0 and y % g_y == 0:
print("YES")
else:
print("NO")
T = int(input())
for _ in range(T):
solve()
发表于 2025-03-26 14:08:47
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
