Codeforces 1478D. Nezzar and Board（貝祖定理）

Codeforces Round #698 (Div. 2) 全文見：https://blog.csdn.net/qq_43461168/article/details/113405897

D. Nezzar and Board

題意：給定一個數組。隻有一種操作。選擇兩個數x，y。然後數組增加一個新數 2*x-y。問能不能通過這種操作合成出 k。

思路參考：https://www.cnblogs.com/HotPants/p/14344386.html

思路： 先變換一下操作。2*x-y = x+(x-y)，然後說是。可以變成 x 加上 任意兩數的內插補點的任意線性組合（暫時沒證出來）。是以最後的k 也就是 a[i] + 任意兩數的差的任意線性組合。這時候就可以用貝祖定理（裴蜀定理）。是以對所有元素求一個gcd。判斷 (k-a[i])%gcd 是否等于0就行了。 然後對于這道題。其實判斷a[1]就行了。因為 a[i] 肯定也和k一樣，可以由任意差的任意組合出來。即(a[i]-a[j])%gcd == 0 一定成立。是以隻需要判斷 (k-a[1])%gcd 就行了。

AC代碼：

#include <iostream>
#include <bits/stdc++.h>
#include <unordered_map>
#define int long long
#define mk make_pair
#define gcd __gcd
using namespace std;
const double eps = 1e-10;
const int mod = 1e9+7;
const int N = 3e6+7;
int n,m,k,t = 1,cas = 1;
int a[N],b[N];
 
signed main(){
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i = 0 ; i < n ; i ++) cin>>a[i];
        int g = a[1]-a[0];
        for(int i = 1 ; i < n ; i ++)  g = gcd(a[i]-a[i-1],g);
        puts((m-a[0]) % g == 0 ? "YES" :"NO");
    }
    return 0;
}