题目

Gym 106114 I。

思路

对于这一类数论的题目，经常会有针对数据范围的分治。

不难发现，二进制下 nn 最多有 log⁡2n≤40\log_2n\le 40 个 11，所以答案一定是 ≤40\le 40 的。

具体地说，我们考虑分解之后的位数。

如果位数是 11 位，要求最高位不为 00，那么此时答案就是 nn，根据上面的结论我们知道 nn 在 >40>40 的时候一定不是答案；

如果两位，n=c1r+c2≤r2−1n=c_1r+c_2\le r^2-1；

如果三位，n=c1r2+c2r+c3≤r3−1n=c_1r^2+c_2r+c_3\le r^3-1；

随着位数的增加，rr 的最小值会不断减小。

我们知道答案 ≤40\le 40，所以可以枚举三个 c1,c2,c3c_1,c_2,c_3，通过求根公式求出是否有这样的 rr，复杂度是 O(log⁡3n)O(\log^3 n)。

这样的话，我们成功处理了 r>n3r>\sqrt[3]{n} 的部分。对于 r≤n3r\le \sqrt[3]{n} 的部分，直接暴力，复杂度是 O(n3log⁡n)O(\sqrt[3]{n}\log n)。

所以总复杂度为 O(tlog⁡3n+tn3log⁡n)O(t\log^3n+t\sqrt[3]{n}\log n)。题解给的枚举两位 O(tlog⁡2n+tnlog⁡n)O(t\log^2n+t\sqrt{n}\log n) 我没有通过，不知道是不是常数太大。

实现

实现上来说，我们可以让 n≤105n\le 10^5 和 R≤n3R\le \sqrt[3]{n} 都直接暴力，保证 RR 和 nn 都充分大，然后根据上面的思路进行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;

#define int long long
int bruteforce(int n, int R) {
    int ans = 1e9;
    for (int r = 2; r <= R; r++) {
        int x = n;
        int sum = 0;
        while (x) {
            sum += x % r;
            x /= r;
        }
        ans = min(ans, sum);
    }
    return ans;
}

int solve(int n, int R) {
    if (n <= 1e5) return bruteforce(n, R);
    
    int m = powl(n, 1.0l / 3.0l);
    if (R <= m) return bruteforce(n, R);
    int ans = bruteforce(n, m);
    for (int c1 = 0; c1 <= ans; c1++) {
        for (int c2 = 0; c1+c2 <= ans; c2++) {
            for (int c3 = 0; c1+c2+c3 <= ans; c3++) {
                if (c1 == 0 && c2 == 0) break;
                if (c1 == 0) {
                    if ((n - c3) % c2) continue;
                    int r = (n - c3) / c2;
                    if (r <= m || r > R || c1 >= r || c2 >= r || c3 >= r) continue;
                    ans = min(ans, c1+c2+c3);
                }
                else {
                    int delta = c2 * c2 - 4 * c1 * (c3 - n);
                    if (delta < 0) continue;
                    int k = sqrtl(delta);
                    if (k * k != delta) continue;
                    if (-c2 + k < 0 || (-c2 + k) % (2 * c1)) continue;
                    int r = (-c2 + k) / (2 * c1);
                    if (r <= m || r > R || c1 >= r || c2 >= r || c3 >= r) continue;
                    ans = min(ans, c1+c2+c3);
                }
            }
        }
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n, R;
        cin >> n >> R;
        cout << solve(n, R) << '\n';
    }
    return 0;
}