千问 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)) 0return (g (g - 1)) 0;}代码说明- gcd 函数标准欧几里得算法用 while 循环实现效率高。- (g (g - 1)) 0位运算判断 2 的幂次方。例如- g 8二进制 1000g-1 7二进制 01111000 0111 0 → 是 2 的幂。- g 6二进制 0110g-1 5二进制 01010110 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看最后是否等于1while (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 测试推荐使用位运算版本更简洁高效。