#P9704. ⾮常简单的数论题

    ID: 6332 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-固定一个变量消去另一维倍数枚举一维前缀和交换求和顺序向下取整与向上取整

⾮常简单的数论题

本题改编自 Codeforces 1223G · Wooden Raft。本站版本另有面积下限 kk。

题目描述

给定一个含 nn 个非负整数的序列 AA。你可以任意次将一个正整数 cc 拆成两个正整数 a,ba,b,要求 a+b=ca+b=c。拆出的数可以继续拆分,剩余的数可以不用。

选定两个整数 x,y≥2x,y\ge2。若拆分后能取出 22 个值为 xx 的数和另外 xx 个值为 yy 的数,则称 (x,y)(x,y) 可行。当 x=yx=y 时,需要共取出 x+2x+2 个相同的数。

求所有可行 (x,y)(x,y) 中 xyxy 的最大值。若不存在可行方案,或这个最大值小于给定的 kk,输出 qinggebaqiliaogewudi。

输入格式

第一行两个整数 n,kn,k,其中 kk 为正整数。

第二行 nn 个整数 A1,A2,…,AnA_1,A_2,\ldots,A_n。若 n=0n=0,无需给出第二行。

输出格式

输出一行。若有可行方案且最大值不小于 kk,输出最大值。否则输出 qinggebaqiliaogewudi。

样例

4 1
4 4 3 2
8

将 33 拆为 2+12+1,取出两个 22 和两个 44,即 (x,y)=(2,4)(x,y)=(2,4)。

8 5
7 1 8 0 6 2 9 1
21

从 8,98,9 各拆出一个 77,再将 66 拆成 3+33+3。可以取出两个 33 和三个 77,即 (x,y)=(3,7)(x,y)=(3,7)。

另有两组附件样例 输入一、输出一 与 输入二、输出二。

数据范围

0≤n,Ai≤5×1050\le n,A_i\le5\times10^5。kk 以十进制给出,可能超过 32 位整数范围。因为 x,yx,y 均不超过 max⁡Ai\max A_i,当 k>2.5×1011k>2.5\times10^{11} 时一定无解。

分组 分值 附加限制
1 10 无
2 20 n≤500n\le500,Ai≤100A_i\le100
3 n≤3000n\le3000,Ai≤2000A_i\le2000
4 25 n,Ai≤105n,A_i\le10^5
5 无