CF1476A - K-divisible Sum

卡题点：看到“最小化最大值”就想二分，但这题其实是纯数学构造 + 取上整。

题意重述

给定 $n,k$，要构造长度为 $n$ 的正整数数组 $a$，满足：

• $S=a_1+\cdots +a_n$ 能被 $k$ 整除
• $max(a)$ 尽量小

输出最小可能的 $max(a)$。

关键观察（把问题变成“区间里有没有 $k$ 的倍数”）

如果我们规定 $max(a)\le M$，那么每个 $a_i\in [1,M]$，所以

$$n\le S\le nM$$

并且任意 $S\in [n,nM]$ 都能被构造出来：从全 1 开始，总和为 $n$，每次把某个元素加 1，最多加到 $M$，总共可以增加 $0..n(M-1)$，因此能覆盖连续区间。

所以存在解当且仅当区间 $[n,nM]$ 中存在一个 $k$ 的倍数。

令

$$S_0=min\{S\ge n\mid k\mid S\}=\lceil \frac{n}{k}\rceil \cdot k$$

那么只要 $nM\ge S_0$ 就行，最小 $M$ 是

$$\boxed{{\displaystyle \lceil \frac{S_0}{n}\rceil }}$$

也就是“两次取上整”：先把总和提到不小于 $n$ 的最小 $k$ 倍数，再把它均摊到 $n$ 个数上。

直接公式（实现时全是整数除法）

设 ceil_div(x,y) = (x+y-1)/y（正整数）。

• S0 = ceil_div(n, k) * k
• ans = ceil_div(S0, n)

复杂度 $O(1)$/case。

为什么一定能构造（理解用，不用真的输出数组）

取 $M=\lceil S_0/n\rceil$，则 $n(M-1)<S_0\le nM$。 从全 $M$ 的数组（和为 $nM$）开始，令 $D=nM-S_0$，有 $0\le D<n$。 把前 $D$ 个元素减 1（变成 $M-1$），其余保持 $M$，和就变成 $S_0$，且最大值仍是 $M$。

参考代码（C++）

#include <bits/stdc++.h>
using namespace std;

static long long ceil_div(long long x, long long y) {
	return (x + y - 1) / y;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t;
	cin >> t;
	while (t--) {
		long long n, k;
		cin >> n >> k;
		long long s0 = ceil_div(n, k) * k;
		long long ans = ceil_div(s0, n);
		cout << ans << "\n";
	}
	return 0;
}

快速自检（对拍脑子）

• n=1,k=5：S0=5，ans=5
• n=4,k=3：S0=6，ans=2
• n=8,k=8：S0=8，ans=1
• n=8,k=17：S0=17，ans=3