傳送門
思路：
從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 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259932.html
標籤：其他
上一篇：重建二叉樹
下一篇：LeetCode做題筆記-135