作者:黑衬衫1994 | 来源:互联网 | 2023-09-06 12:14
CF1477(gcd,构造)题意给出一个序列\(a\),可以用它们按如下规则无限生成数字。从\(a\)中选择一对数\(x,y\)。将\(2x-y\)加入序列。现在给出目标\(k\)
CF1477(gcd,构造)
题意
给出一个序列 \(a\),可以用它们按如下规则无限生成数字。
- 从 \(a\) 中选择一对数 \(x,y\) 。
- 将 \(2x- y\) 加入序列。
现在给出目标 \(k\) 。问能否有原来序列生成。
题意
如果我们注意到 \(2x-y = x+(x-y)\) 。
我们设 \(d = (x-y)\) 。
如果我们以 \(x_1\) 为起点构造,可以发现 \(k = \sum d*p+x_1\) 的形式,\(p\) 是任意整数。此时可以在 \(O(n^2)\) 时间判断。
又注意到 \(x_1-x_2+x_3-x_1 = x_3-x_2\) 也就是说其他起点构成的 \(d\) 可以用这样的方法构造,假定 \(x_1=0\) 就仅需判断 \(k = \sum d*p\) 是否成立,又因为 \(gcd(x_{1,2,3..,n})|x-y\) 。因此 \(gcd(x_{1,2,3..,n})|k\) 。判断这个即可。
如果 \(x_1 > 0\) 。序列整体减去 \(x_1\) 之后判断等价问题 \(gcd(x_{1,2,3..,n})|(k-x_1)\) 即可。
import sys
from collections import defaultdict, deque,Counter
import heapq
input = sys.stdin.readline
from math import *
def mrd(): return [int(x) for x in input().split()]
def rd(): return int(input())
MAXN = 2 * 10**5 + 5
INF = 10**16 * 2
mod = 10**9 + 7
#----------------------------------------------------------------------------------#
def solve():
n,k = mrd()
a = mrd()
g = 0
for i in range(n): g = gcd(a[i] - a[0],g)
print(g)
if (k - a[0]) % g == 0:
print("YES")
else:
print("NO")
if __name__ == "__main__":
for _ in range(rd()):
solve()