CF 1477A. Nezzar and Board

• 2021 年 2 月 15 日
• 筆記
• CF

傳送門

思路：

從k = 2 * x – y ==> 2 * x = k + y ，可以看出x是k,y的中間值，則如果存在x1,x2，且x1 = x2 ± 1，則通過x1,x2可以得到所有整數，則任意的k都成立。

例如：2 3 ===>  2 3 4 ===>   1 2 3 4 …… 

對於該數組A： （0 6 9 12 20），我們可以得到a[i] – a[i – 1]的數組（6，3，3，8）。

可以得到A對於元素可以表示一個集合：

a[1] -> a[1] + 6 * n

a[2] -> a[2] + 3 * n

a[3] -> a[3] + 3 * n

a[4] -> a[4] + 8 * n

而我們只需要確認，這些集合合併之後是否存在x1,x2且x1 =  x2 ± 1.

我們任取兩個集合 a(x) + p * n , a(y) + q * m（n,m ∈ Z）,則需要存在

　　a(x) – p * n – ( a(y) + q * m ) = 1 

==> q * m – p * n = 1 * (1 – a(x) + a(y)) 有解，假設右邊為T，則gcd(p, m) | T,如果a[i] – a[i-1]數組中存在兩個差值的gcd = 1，則一定有解。我們只需求gcd(a[i – 1] – a[i], a[i – 2] – a[i – 1]….) = GCD判斷是不是1即可，如果為1，則可以說明所有A集合合併後可以表示為 a[1] + n （n∈Z），即一定有解；如果不為1，所有數合併的集合也可以表示為a[1] + GCD * n （n∈Z），判斷k是不是屬於a[1] + GCD * n的集合的一個元素即可。

當然以上是通過樣例推出，不嚴謹，以下給出其中一個遺漏點的證明。

假設數組：

a b c d 如果 2 * b – a = key ,則

a b c key d

我們需要證明gcd(b – a, c – b, d – c) = gcd(b – a, c – b, 2 * b – a – c, d – (2 * b – a) ),通過gcd的兩個性質：

①gcd(a, b, c) = gcd(a, gcd(b, c))

②gcd(a, b) = gcd(a, b – a) = gcd(a, b + a)

假設gcd(b – a, c – b, 2 * b – a – c, d – (2 * b – a) ) = T， 

T = gcd(b – a, c – b,   gcd(2 * b – a – c, d – (2 * b – a)  )       )

通過  d – (2 * b – a) + (2 * b – a – c) = d – c，

T = gcd(…,  gcd(2 * b – a – c, d – c)) 

T = gcd(b – a, d – c,  gcd(c – b, 2 * b – a – c)   )

通過  2 * b – a – c – (c – b) = b – a

T = gcd(b – a , c – b, c – d),所以左邊=右邊。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 #define ll long long
 5 
 6 const int N = 3e5 + 10;
 7 ll a[N];
 8 
 9 void solve()
10 {
11     int T;
12     cin >> T;
13     while(T--) {
14         int n;
15         ll k;
16         cin >> n >> k;
17         for(int i = 1; i <= n; ++i) cin >> a[i];
18         ll gcd = 0;
19         for(int i = 2;  i <= n; ++i) {
20             gcd = __gcd(gcd, a[i] - a[i - 1]);
21         }
22         if(abs(a[1] - k) % gcd) cout << "NO" << endl;
23         else cout << "YES" << endl;
24     }
25 }
26 
27 int main(){
28 
29     ios::sync_with_stdio(false);
30     cin.tie(0); cout.tie(0);
31     solve();
32 
33     return 0;
34 }