#P5956. [Usaco2022 Feb]Sleeping in Class P

    ID: 4956 传统题 1500ms 512MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>难度分类提高+/省选-排序与序列处理一维前缀和数论欧几里得算法试除法分解质因数整除 Zeta 变换CF2600

[Usaco2022 Feb]Sleeping in Class P

题目描述

Farmer John 的课常常让 Bessie 打瞌睡。Elsie 记下了每节课 Bessie 打瞌睡的次数。共有 NN 节课,第 ii 节课打瞌睡 aia_i 次。Elsie 想把记录改成每节课打瞌睡的次数都一样。

一次修改可以将相邻的两项合并成它们的和,或把一项拆成两个任意的非负整数,它们的和等于原来的数。比如将 [1,2,3,4,5][1,2,3,4,5] 的第 22 和第 33 项合并,得到 [1,5,4,5][1,5,4,5]。然后拆分第三项,可以把 44 换成 (0,4)(0,4)、(1,3)(1,3)、(2,2)(2,2)、(3,1)(3,1) 或 (4,0)(4,0)。

给定 QQ 个候选值 qiq_i。对于每个 qiq_i,从原始记录出发,求把记录变成每一项都恰好等于 qiq_i 所需的最少修改次数。

输入格式

第一行一个整数 NN(2≤N≤1052\le N\le10^5)。第二行 NN 个整数 aia_i(1≤ai≤10181\le a_i\le10^{18}),且 ∑iai≤1018\sum_i a_i\le10^{18}。

第三行一个整数 QQ(1≤Q≤1051\le Q\le10^5)。接下来 QQ 行,每行给出一个 qiq_i(1≤qi≤10181\le q_i\le10^{18})。

输出格式

对每个 qiq_i,输出一行,写出最少修改次数。若无法使所有项都等于 qiq_i,输出 -1。

样例 #1

样例输入 #1

6
1 2 3 1 1 4
7
1
2
3
4
5
6
12

样例输出 #1

6
6
4
5
-1
4
5

样例解释 #1

要使每项都等于 33,至少需要 44 次修改。一种做法为 $[1,2,3,1,1,4]\to[3,3,1,1,4]\to[3,3,1,5]\to[3,3,6]\to[3,3,3,3]$。无法使每项都等于 55,故该询问输出 −1-1。

测试点性质

  • 测试点 2–4 满足 N,Q≤5000N,Q\le5000。
  • 测试点 5–7 中,每个 ai≤109a_i\le10^9。
  • 测试点 8–26 无额外限制。