目录
裴蜀定理
OJ实战
力扣 1250. 检查「好数组」
力扣 2543. 判断一个点是否可以到达
裴蜀定理
裴蜀定理：若a,b是整数，且gcd(a,b)=d，那么对于任意的整数x,y，ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。
OJ实战
力扣 1250. 检查「好数组」
给你一个正整数数组 nums，你需要从中任选一些子集，然后将子集中每一个数乘以一个 任意整数，并求出他们的和。
假如该和结果为 1，那么原数组就是一个「好数组」，则返回 True；否则请返回 False。
示例 1：
输入：nums = [12,5,7,23] 输出：true 解释：挑选数字 5 和 7。 5*3 + 7*(-2) = 1
示例 2：
输入：nums = [29,6,10] 输出：true 解释：挑选数字 29, 6 和 10。 29*1 + 6*(-3) + 10*(-1) = 1
示例 3：
输入：nums = [3,6] 输出：false
提示：
1 <= nums.length <= 10^51 <= nums[i] <= 10^9
class Solution {
public:
bool isGoodArray(vector<int>& nums) {
auto ans=0;
for(auto x:nums){
ans=gcd(ans,x);
}
return ans==1;
}
long long gcd(long long a, long long b)
{
return b ? gcd(b, a%b) : a;
}
};力扣 2543. 判断一个点是否可以到达
给你一个无穷大的网格图。一开始你在 (1, 1) ，你需要通过有限步移动到达点 (targetX, targetY) 。
每一步 ，你可以从点 (x, y) 移动到以下点之一：
(x, y - x)(x - y, y)(2 * x, y)(x, 2 * y)
给你两个整数 targetX 和 targetY ，分别表示你最后需要到达点的 X 和 Y 坐标。如果你可以从 (1, 1) 出发到达这个点，请你返回true ，否则返回 false 。
示例 1：
输入：targetX = 6, targetY = 9 输出：false 解释：没法从 (1,1) 出发到达 (6,9) ，所以返回 false 。
示例 2：
输入：targetX = 4, targetY = 7 输出：true 解释：你可以按照以下路径到达：(1,1) -> (1,2) -> (1,4) -> (1,8) -> (1,7) -> (2,7) -> (4,7) 。
提示：
1 <= targetX, targetY <= 109
思路：把4个操作分2类，前2个使得gcd不变，后2个使得gcd不变或者乘2文章来源：https://www.toymoban.com/news/detail-624726.html
再根据裴蜀定理，gcd为1的点都可以到达(1,1)点。文章来源地址https://www.toymoban.com/news/detail-624726.html
class Solution {
public:
bool isReachable(int targetX, int targetY) {
int g = Gcd(targetX, targetY);
return (g&-g) == g;
}
};到了这里，关于裴蜀定理的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[电路]14-叠加定理和齐性定理](https://imgs.yssmx.com/Uploads/2024/02/455911-1.png)
