[COCI 2009/2010 #2] FAKTOR

题意

给出 A 和 I，求最小的正整数 N，使得 ceil(N / A) >= I。

思路

先看一个可以直接验证想法的朴素解：

可以从 N = 1 开始往上枚举，找到第一个满足 ceil(N / A) >= I 的数。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18#include <bits/stdc++.h>
using namespace std;

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

    long long A, I;
    cin >> A >> I;

    long long N = 1;
    while ((N + A - 1) / A < I) {
        N++;
    }

    cout << N << '\n';
    return 0;
}

不过这题其实可以直接化公式。因为

text

1ceil(N / A) >= I

等价于

text

1N > A * (I - 1)

所以最小的正整数解就是 A * (I - 1) + 1。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12#include <bits/stdc++.h>
using namespace std;

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

    long long A, I;
    cin >> A >> I;
    cout << A * (I - 1) + 1 << '\n';
    return 0;
}

复杂度

main.cpp 是直接公式，时间复杂度 $O(1)$ ，空间复杂度 $O(1)$ 。

总结

把上取整条件改写成严格不等式后，答案就变成了一个非常直接的整数公式。

[COCI 2009/2010 #2] FAKTOR

目录

题意

思路

代码

复杂度

总结