[AHOI2018初中组] 根式化简

题意

给出 n 个正整数 x。

对每个 x，要求找最大的整数 a，使得存在整数 b 满足：

text

1a^3 * b = x

只输出这个最大的 a。

思路

先看一个小数据暴力版：

cpp

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
62
63
64
65
66
67
68
69#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;

const int MAXN = 1005;

int n;
ull x_arr[MAXN];

// brute.cpp：小数据暴力版。
// 直接做试除分解，统计每个质因子的指数 e，
// 把 floor(e / 3) 部分乘回答案。

ull solve_one(ull x) {
    ull ans = 1;

    for (ull p = 2; p * p * p <= x; p++) {
        if (x % p != 0) {
            continue;
        }

        int cnt = 0;
        while (x % p == 0) {
            x /= p;
            cnt++;
        }

        while (cnt >= 3) {
            ans *= p;
            cnt -= 3;
        }
    }

    // 剩下的部分如果还能贡献给答案，只可能本身就是一个完整立方数。
    ull l = 1, r = 1000000, cube_root = 0;
    while (l <= r) {
        ull mid = (l + r) >> 1;
        __int128 val = (__int128)mid * mid * mid;
        if (val <= x) {
            cube_root = mid;
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }
    if ((__int128)cube_root * cube_root * cube_root == x) {
        ans *= cube_root;
    }

    return ans;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x_arr[i];
    }

    for (int i = 1; i <= n; i++) {
        cout << solve_one(x_arr[i]) << '\n';
    }

    return 0;
}

这题的根式外形其实只是表面。

如果把 x 分解成：

text

1x = p1^e1 * p2^e2 * ... * pk^ek

那么能提出到立方根外面的部分，显然就是每个指数里完整的 3 个一组：

text

1a = p1^(floor(e1 / 3)) * p2^(floor(e2 / 3)) * ... * pk^(floor(ek / 3))

所以题目的数学部分很短，真正难点只剩下一个：

如何在 10^18 范围内快速分解整数

这里使用 Miller Rabin + Pollard Rho：

Miller Rabin 快速判断一个数是不是素数
Pollard Rho 找一个非平凡因子
递归下去直到全部拆成质因子

分解完成后，把相同质因子出现次数统计出来，再按 cnt / 3 把它对答案的贡献乘回去即可。

代码

cpp

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;
using u128 = __uint128_t;

const int MAXN = 10005;

int n;
ull x_arr[MAXN];
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ull mul_mod(ull a, ull b, ull mod) {
    return (u128) a * b % mod;
}

ull pow_mod(ull a, ull b, ull mod) {
    ull res = 1;
    while (b > 0) {
        if (b & 1ULL) {
            res = mul_mod(res, a, mod);
        }
        a = mul_mod(a, a, mod);
        b >>= 1;
    }
    return res;
}

bool miller_rabin(ull n) {
    if (n < 2) {
        return false;
    }

    ull test_prime[] = {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL, 19ULL, 23ULL, 29ULL, 31ULL, 37ULL};
    for (int i = 0; i < 12; i++) {
        ull p = test_prime[i];
        if (n % p == 0) {
            return n == p;
        }
    }

    ull d = n - 1;
    int s = 0;
    while ((d & 1ULL) == 0) {
        d >>= 1;
        s++;
    }

    // 这组底数对 unsigned long long 范围内的数是确定正确的。
    ull base_arr[] = {2ULL, 325ULL, 9375ULL, 28178ULL, 450775ULL, 9780504ULL, 1795265022ULL};
    for (int i = 0; i < 7; i++) {
        ull a = base_arr[i] % n;
        if (a == 0) {
            continue;
        }

        ull x = pow_mod(a, d, n);
        if (x == 1 || x == n - 1) {
            continue;
        }

        bool ok = false;
        for (int r = 1; r < s; r++) {
            x = mul_mod(x, x, n);
            if (x == n - 1) {
                ok = true;
                break;
            }
        }

        if (!ok) {
            return false;
        }
    }

    return true;
}

ull pollard_rho(ull n) {
    if ((n & 1ULL) == 0) {
        return 2;
    }

    while (true) {
        ull c = uniform_int_distribution<ull>(1, n - 1)(rng);
        ull x = uniform_int_distribution<ull>(0, n - 1)(rng);
        ull y = x;
        ull d = 1;

        while (d == 1) {
            x = (mul_mod(x, x, n) + c) % n;
            y = (mul_mod(y, y, n) + c) % n;
            y = (mul_mod(y, y, n) + c) % n;

            ull diff = x > y ? x - y : y - x;
            d = gcd(diff, n);
        }

        if (d != n) {
            return d;
        }
    }
}

void factorize(ull n, vector<ull> &fac) {
    if (n == 1) {
        return;
    }
    if (miller_rabin(n)) {
        fac.push_back(n);
        return;
    }

    ull d = pollard_rho(n);
    factorize(d, fac);
    factorize(n / d, fac);
}

ull int_pow(ull a, int e) {
    ull res = 1;
    for (int i = 1; i <= e; i++) {
        res *= a;
    }
    return res;
}

ull solve_one(ull x) {
    if (x == 1) {
        return 1;
    }

    vector<ull> fac;
    factorize(x, fac);
    sort(fac.begin(), fac.end());

    ull ans = 1;
    for (int i = 0, j; i < (int)fac.size(); i = j) {
        j = i;
        while (j < (int)fac.size() && fac[j] == fac[i]) {
            j++;
        }
        int cnt = j - i;
        ans *= int_pow(fac[i], cnt / 3);
    }
    return ans;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x_arr[i];
    }

    for (int i = 1; i <= n; i++) {
        cout << solve_one(x_arr[i]) << '\n';
    }

    return 0;
}

复杂度

Pollard Rho 的严格复杂度不容易写成一个很整齐的式子。

在竞赛中通常认为：

Miller Rabin 判素很快
Pollard Rho 对 10^18 范围分解足够高效

空间复杂度很小，可以认为是 $O(log x)$ 级别。

总结

这题真正的核心其实只有一句话：

质因子指数每满 3 个，就能给答案贡献一个这个质因子

数学结论本身不难，难点完全在大整数分解实现。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

[AHOI2018初中组] 根式化简

目录

题意

思路

代码

复杂度

总结

一图流解析