千问 LeetCode 2543. 判断一个点是否可以到达 C语言实现
这道题的核心是从终点反向推导，利用最大公约数（GCD） 的性质来判断。C语言实现与Java思路完全一致，只是语法略有不同。
核心结论
从 (targetX, targetY) 能反向到达 (1, 1) 的充要条件是：
gcd(targetX, targetY) 是 2 的幂次方（即形如 1, 2, 4, 8, 16...）。
判断一个数 g 是否为 2 的幂次方：g > 0 且 (g & (g - 1)) == 0。
C语言实现
// 辗转相除法求最大公约数
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
bool isReachable(int targetX, int targetY) {
// 1. 计算最大公约数
int g = gcd(targetX, targetY);
// 2. 判断 g 是否为 2 的幂次方
// g > 0 且 (g & (g - 1)) == 0
return (g & (g - 1)) == 0;
}
代码说明
- gcd 函数：标准欧几里得算法，用 while 循环实现，效率高。
- (g & (g - 1)) == 0：位运算判断 2 的幂次方。例如：
- g = 8（二进制 1000），g-1 = 7（二进制 0111），1000 & 0111 = 0 → 是 2 的幂。
- g = 6（二进制 0110），g-1 = 5（二进制 0101），0110 & 0101 = 0100 ≠ 0 → 不是 2 的幂。
- bool 类型：C语言需要包含 <stdbool.h> 头文件（LeetCode 环境已默认包含）。
- 时间复杂度：O(log min(targetX, targetY))。
- 空间复杂度：O(1)。
另一种写法（直接除2法）
如果你对位运算不太熟悉，也可以用循环除2的方式判断：
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
bool isReachable(int targetX, int targetY) {
int g = gcd(targetX, targetY);
// 不断除以2，看最后是否等于1
while (g % 2 == 0) {
g /= 2;
}
return g == 1;
}
示例验证
输入 GCD 是否为2的幂 结果
(6, 9) 3 否 false
(4, 7) 1 是 true
(8, 12) 4 是 true
(10, 15) 5 否 false
(1, 1) 1 是 true
两种写法都可以通过 LeetCode 测试，推荐使用位运算版本，更简洁高效。