CF 1477A. Nezzar and Board

传送门

思路：

从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 }

巴特西

CF 1477A. Nezzar and Board

最新文章

热门文章