题解 | 小苯的数字权值

刚开始以为无脑拆就行了后来发现70这个数字就不是这样

虽然可能有更简单的解时间复杂度更优（不知道有没有但感觉应该是有的）

但是我这里有一种不要脑子的做法，只需要会简单的dp和调和级数预处理因子就行

预处理时间复杂度O(NlogN),查询O(1),空间复杂度O(NlogN)，其中N是2e5

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

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    cin >> T;
    vector<int> a(200010, 0);
    vector<vector<int>> g(200010);
    for (int i = 1; i <= 200000; ++i) {
        for (int j = i; j <= 200000; j += i) {
            ++a[j];
        }
    }
    for (int i = 2; i <= 200000; ++i) {
        for (int j = i * 2; j <= 200000; j += i) {
            g[j].push_back(i);
        }
    }
    vector<int> dp(200010);
    for (int i = 2; i <= 200000; ++i) {
        dp[i] = a[i];
        for (auto v : g[i]) {
            dp[i] = max(dp[v] + dp[i / v], dp[i]);
        }
    }
    while (T--) {
        int n;
        cin >> n;
        cout << dp[n] << '\n';
    }
    return 0;
}

也是找到了更优秀的解法了

他是单质因子的多少次幂的情况就是拆开更好

否则都是不拆更好

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

void solve() {
    int x;
    cin >> x;
    int res = 0, sum = 1;
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            int cnt = 0;
            while (x % i == 0)
                x /= i, ++cnt;
            sum *= cnt + 1;
            res = max(res, cnt * 2);
        }
    }
    if (x > 1)
        res = max(res, 2), sum *= 2;
    cout << max(res, sum) << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}