目錄
裴蜀定理
OJ實(shí)戰(zhàn)
力扣?1250. 檢查「好數(shù)組」
力扣?2543. 判斷一個(gè)點(diǎn)是否可以到達(dá)
裴蜀定理
裴蜀定理：若a,b是整數(shù)，且gcd(a,b)=d，那么對(duì)于任意的整數(shù)x,y，ax+by都一定是d的倍數(shù)，特別地，一定存在整數(shù)x,y，使ax+by=d成立。
OJ實(shí)戰(zhàn)
力扣?1250. 檢查「好數(shù)組」
給你一個(gè)正整數(shù)數(shù)組?nums，你需要從中任選一些子集，然后將子集中每一個(gè)數(shù)乘以一個(gè)?任意整數(shù)，并求出他們的和。
假如該和結(jié)果為?1，那么原數(shù)組就是一個(gè)「好數(shù)組」，則返回?True；否則請(qǐng)返回?False。
示例 1：
輸入：nums = [12,5,7,23] 輸出：true 解釋：挑選數(shù)字 5 和 7。 5*3 + 7*(-2) = 1
示例 2：
輸入：nums = [29,6,10] 輸出：true 解釋：挑選數(shù)字 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. 判斷一個(gè)點(diǎn)是否可以到達(dá)
給你一個(gè)無(wú)窮大的網(wǎng)格圖。一開(kāi)始你在?(1, 1)?，你需要通過(guò)有限步移動(dòng)到達(dá)點(diǎn)?(targetX, targetY)?。
每一步?，你可以從點(diǎn)?(x, y)?移動(dòng)到以下點(diǎn)之一：
(x, y - x)(x - y, y)(2 * x, y)(x, 2 * y)
給你兩個(gè)整數(shù)?targetX?和?targetY?，分別表示你最后需要到達(dá)點(diǎn)的 X 和 Y 坐標(biāo)。如果你可以從?(1, 1)?出發(fā)到達(dá)這個(gè)點(diǎn)，請(qǐng)你返回true?，否則返回?false?。
示例 1：
輸入：targetX = 6, targetY = 9 輸出：false 解釋：沒(méi)法從 (1,1) 出發(fā)到達(dá) (6,9) ，所以返回 false 。
示例 2：
輸入：targetX = 4, targetY = 7 輸出：true 解釋：你可以按照以下路徑到達(dá)：(1,1) -> (1,2) -> (1,4) -> (1,8) -> (1,7) -> (2,7) -> (4,7) 。
提示：
1 <= targetX, targetY?<= 109
思路：把4個(gè)操作分2類，前2個(gè)使得gcd不變，后2個(gè)使得gcd不變或者乘2文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-624726.html
再根據(jù)裴蜀定理，gcd為1的點(diǎn)都可以到達(dá)(1,1)點(diǎn)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-624726.html
class Solution {
public:
bool isReachable(int targetX, int targetY) {
int g = Gcd(targetX, targetY);
return (g&-g) == g;
}
};到了這里，關(guān)于裴蜀定理的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[電路]14-疊加定理和齊性定理](https://imgs.yssmx.com/Uploads/2024/02/455911-1.png)
