#P9704. ⾮常简单的数论题

⾮常简单的数论题

Source:CF1223G。

题目描述

来⾃ fot 机房的⼩ L,给了你⼀个序列 AA。由于序列的不稳定性,它会随机将⼀个数 cc 分解为 a,ba,ba+b=ca+b=c,可以分解多次。令操作完的序列为 BB

之后,⼩ L 给定你⼀个 kk 并询问你,当前存在的所有可能的序列 BB 中,是否存在⼀个⼆元组 (x,y)(x,y),满⾜:

  1. 可以从 BB 中取出 22xxxxyy
  2. x2x\ge 2y2y\ge 2xkx\ge k

如果对于任意可能的序列不存在这样的⼆元组,输出 qinggebaqiliaogewudi,否则输出 xyxy 的最小值。

输入格式

输⼊第⼀⾏,是两个正整数 n,kn,k,分别表⽰初始 AA 序列中数的个数和⼩ L 给你的数。

接下来⼀⾏,共 nn 个数,表⽰ AA 中各个数。

输出格式

输出⼀个数,表⽰你求得的答案;或是⼀个字符串,表⽰不存在这样的⼆元组。

样例

4 1
4 4 3 2
8

33 分解为 2211 时,有 (2,4)(2,4) 可以取到 88。可以证明不存在更优解。

8 5
7 1 8 0 6 2 9 1
21

8899 各分解出⼀个 77 时,有 (3,7)(3,7) 可以取到 2121。可以证明不存在更优解。

数据范围

对于前 10%10\% 的数据,k=9800k=9800

对于前 30%30\% 的数据,n500n\le 500Ai100A_i\le 100

对于前 50%50\% 的数据,n3000n\le 3000Ai2000A_i\le 2000

对于前 75%75\% 的数据,n,Ai105n,A_i\le 10^5

对于前 100%100\% 的数据,0n,Ai5×1050\le n,A_i\le 5\times 10^5