K-divisible Sum
题目描述
You are given two integers
n
n
n and
k
k
k.
You should create an array of
n
n
n positive integers
a
1
,
a
2
,
…
,
a
n
a_1, a_2, \dots, a_n
a1,a2,…,an such that the sum
(
a
1
+
a
2
+
⋯
+
a
n
)
(a_1 + a_2 + \dots + a_n)
(a1+a2+⋯+an) is divisible by
k
k
k and maximum element in
a
a
a is minimum possible.
What is the minimum possible maximum element in
a
a
a?
输入描述
The first line contains a single integer
t
t
t (
1
≤
t
≤
1000
1 \le t \le 1000
1≤t≤1000) — the number of test cases.
The first and only line of each test case contains two integers
n
n
n and
k
k
k (
1
≤
n
≤
1
0
9
1 \le n \le 10^9
1≤n≤109;
1
≤
k
≤
1
0
9
1 \le k \le 10^9
1≤k≤109).
输出描述
For each test case, print one integer — the minimum possible maximum element in array
a
a
a such that the sum
(
a
1
+
⋯
+
a
n
)
(a_1 + \dots + a_n)
(a1+⋯+an) is divisible by
k
k
k.
样例 #1
样例输入 #1
4
1 5
4 3
8 8
8 17
样例输出 #1
5
2
1
3
提示
In the first test case
n
=
1
n = 1
n=1, so the array consists of one element
a
1
a_1
a1 and if we make
a
1
=
5
a_1 = 5
a1=5 it will be divisible by
k
=
5
k = 5
k=5 and the minimum possible.
In the second test case, we can create array
a
=
[
1
,
2
,
1
,
2
]
a = [1, 2, 1, 2]
a=[1,2,1,2]. The sum is divisible by
k
=
3
k = 3
k=3 and the maximum is equal to
2
2
2.
In the third test case, we can create array
a
=
[
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
]
a = [1, 1, 1, 1, 1, 1, 1, 1]
a=[1,1,1,1,1,1,1,1]. The sum is divisible by
k
=
8
k = 8
k=8 and the maximum is equal to
1
1
1.
原题
CF——传送门
思路
我们把
s
u
m
sum
sum 表示为数组
a
a
a 的和。因为
s
u
m
sum
sum 能被
k
k
k 整除，所以令
s
u
m
=
n
u
m
⋅
k
sum = num \cdot k
sum=num⋅k。同时又因为所有的
a
i
a_i
ai 都是正数，所以
s
u
m
≥
n
sum \ge n
sum≥n。显然，
s
u
m
sum
sum 的值越小，最大值
a
m
a
x
a_{max}
amax 就越小，所以我们需找到使得
s
u
m
≥
n
sum \ge n
sum≥n 成立的最小的
n
u
m
num
num，即
⌈
n
k
⌉
\left\lceil \frac{n}{k} \right\rceil
⌈kn⌉。确定了
n
u
m
num
num 的值后，
s
u
m
sum
sum 的值也就确定了，即
s
u
m
=
n
u
m
⋅
k
sum = num \cdot k
sum=num⋅k。
那么剩下的问题就是：和为
s
u
m
sum
sum，长度为
n
n
n 的数组，如何构造使得其中的最大值最小 ？对于这个问题，我们利用贪心的思想，在数组的
n
n
n 个位置上逐个地填补
1
1
1，循环这个操作直至
s
u
m
sum
sum 拆成
s
u
m
sum
sum 个
1
1
1 后全部被填补到数组里。通过这样的方式，我们总是可以构造出数组
a
a
a ，它的和等于
s
u
m
sum
sum，长度等于
n
n
n，最大元素的值等于
⌈
s
n
⌉
\left\lceil \frac{s}{n} \right\rceil
⌈ns⌉ 。
代码
#include
using namespace std;
using i64 = long long;
typedef long long ll;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
i64 n, k;
cin >> n >> k;
i64 num = ceil(1.0 * n / k);
i64 sum = num * k;
i64 maxn = ceil(1.0 * sum / n);
cout << maxn << '
';
}
return 0;
}
