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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24