我们发现i ≥ sqrt(n)时,每次更新的乘数即ceil(n / i)是不变的
假设i * x更新了n以后,用(i + 1) * y更新,则
(i + 1) * y ≥ i * x =>
y ≥ x * i / (i + 1) =>
y ≥ x - x / (i + 1)
也即x < i + 1时, ceil(n / i)不变,此时i ≥ sqrt(n)
于是模拟一遍什么的就好啦~
1 /**************************************************************
2 Problem: 3858
3 User: rausen
4 Language: C++
5 Result: Accepted
6 Time:112 ms
7 Memory:804 kb
8 ****************************************************************/
9
10 #include <cstdio>
11
12 using namespace std;
13 typedef long long ll;
14
15 int tot;
16 ll n, k;
17
18 int main() {
19 ll i;
20 while (scanf("%lld%lld", &n, &k), n || k) {
21 for (i = 2; i <= k; ++i) {
22 ll tmp = (n + i - 1) / i;
23 if (tmp <= i) {
24 n = tmp * k;
25 break;
26 }
27 n = tmp * i;
28 }
29 printf("Case #%d: %lld\n", ++tot, n);
30 }
31 return 0;
32 }
View Code
转载于:https://www.cnblogs.com/rausen/p/4297717.html