题解 | #小苯的数字权值#

把数字拆成质因数 x 后，x 的权值为 2。

在质因数只有一种的时候，例如 8 = 2 * 2 * 2， 如果不拆的话可以得到的权值和为 4（1，2，4，8） 。如果拆开的话可以拆成 3个2，权值和为3 * 2。

在质因数有多种时，例如70 = 2 * 5 * 7，不拆的话可以得到的权值和为 8（1，2，5，7，10，14，35，70）。如果拆开的话可以拆成 3个2，权值和为3 * 2。

关于所有因数之和，有一个公式 ，sum = (p[0]+1)*(p[1]+1)*......*(p[n]+1)。其中 p[i] 表示第 i 个质因子的个数。这个原理是乘法原理（？）一共有 y 个质因数 x，可以取 [0, y] 个，总共 y + 1 种取法。所以求和的时候每项需要+1。

然后就是注意取质因数的时候加一句 if (x * x > n) break； 这句话可以使得复杂度由 O(T * n) 降为 O (T * sqrt(n))

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

vector<int> prime;
int vis[200010];
void init(int n) {
    for (int i = 2; i <= n; i ++) {
        if (!vis[i]) prime.push_back(i);
        for (auto j : prime) {
            if (i * j > n) break;
            vis[i * j] = 1;
            if (i % j == 0) break;
        }
    }
}
int main() {
    int T;
    cin >> T;
    init(1000);
    for (int n; T --> 0; ) {
        cin >> n;
        map<int, int> mp;
        for (auto x : prime) {
            while (n % x == 0) n /= x, mp[x] ++;
            if (x * x > n) break;
        }
        if (n != 1) {
            mp[n] ++;
        }
        if (mp.size() == 1) {
            auto x = mp.begin();
            cout << x->second * 2 << "\n";
        } else {
            int ans = 1;
            for (auto [x, y] : mp) ans *= (y + 1);
            cout<< ans << "\n";
        }
    }
}