A3148. Ethan王子的最大因子挑战
编程题
普及-
知识点
题目描述
> 注意:本题需要使用freopen进行判题
> 输入文件名:Prince.in
> 输出文件名:Prince.out
Ethan 王子是一位年轻而智慧的君主，他热衷于数学和谜题。在他统治的王国里，有一个传统，就是通过解决复杂的数学问题来展示智慧和力量。一天，Ethan 王子收到了一个数学挑战，要求他找到一个正整数数组 $A$ 和一个正整数 $k$ 的最大的数 $d$。这个数 $d$ 必须满足特定的条件，这个条件就是通过向上取整操作后，一系列的和必须大于等于 $k$。Ethan 王子决定接受这个挑战，展示他的数学天赋。
---
现在给你一个正整数数组 $A$ 和一个正整数 $k$。
希望你求出最大的数 $d$ 满足：
$$ \lceil \frac{a_0}{d} \rceil + \lceil \frac{a_1}{d} \rceil + \lceil \frac{a_2}{d} \rceil + \cdots + \lceil \frac{a_{n-1}}{d} \rceil \geq k $$
题目保证有解。
条件：
1. $d$ 为整数且不超过数组 $A$ 中的最大值
2. $\lceil x \rceil$ 是对 $x$ 向上取整（例如 $\lceil 1.1 \rceil = 2$）
Problem Credits: [Macw07](https://www.acgo.cn/person/929871)。
> 输入文件名:Prince.in
> 输出文件名:Prince.out
Ethan 王子是一位年轻而智慧的君主，他热衷于数学和谜题。在他统治的王国里，有一个传统，就是通过解决复杂的数学问题来展示智慧和力量。一天，Ethan 王子收到了一个数学挑战，要求他找到一个正整数数组 $A$ 和一个正整数 $k$ 的最大的数 $d$。这个数 $d$ 必须满足特定的条件，这个条件就是通过向上取整操作后，一系列的和必须大于等于 $k$。Ethan 王子决定接受这个挑战，展示他的数学天赋。
---
现在给你一个正整数数组 $A$ 和一个正整数 $k$。
希望你求出最大的数 $d$ 满足：
$$ \lceil \frac{a_0}{d} \rceil + \lceil \frac{a_1}{d} \rceil + \lceil \frac{a_2}{d} \rceil + \cdots + \lceil \frac{a_{n-1}}{d} \rceil \geq k $$
题目保证有解。
条件：
1. $d$ 为整数且不超过数组 $A$ 中的最大值
2. $\lceil x \rceil$ 是对 $x$ 向上取整（例如 $\lceil 1.1 \rceil = 2$）
Problem Credits: [Macw07](https://www.acgo.cn/person/929871)。
输入格式
第一行是两个正整数 $n$ 和 $k$，$n$ 是数组 $A$ 的长度，$k$ 是正整数。
接下来的 $n$ 行，每行有一个 $1$ 到 $1000000$ 之间的正整数，表示数组 $A$ 中的元素。
接下来的 $n$ 行，每行有一个 $1$ 到 $1000000$ 之间的正整数，表示数组 $A$ 中的元素。
输出格式
输出最大的数 $d$。
输入输出样例
输入 #1
5 6 1 2 3 4 5
输出 #1
4
说明/提示
$\lceil \frac{1}{4} \rceil = 1$, $\lceil \frac{2}{4} \rceil = 1$, $\lceil \frac{3}{4} \rceil = 1$, $\lceil \frac{4}{4} \rceil = 1$, $\lceil \frac{5}{4} \rceil = 2$, $1 + 1 + 1 + 1 + 2 = 6$。
向上取整可以使用
## 数据范围
$1 \leq n \leq 100000$, $1 \leq k \leq 1000000$
向上取整可以使用
cmath 中的 ceil 方法。## 数据范围
$1 \leq n \leq 100000$, $1 \leq k \leq 1000000$