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

，随便举几个例子，可以发现结论：

• 当时，我们把全部拆开，这样可以得到权值是；
• 当时，全部拆开得到的权值，合并全部得到的权值为，后面明显更大，而且发现如果将进行拆分，那么一定不会更优。

所以写的时候只需要注意特判就好。

#include <iostream>
#include <vector>
using namespace std;
const int N = 2e5 + 10;
vector<int> primes;
bool vis[N];
void init() {
    vis[0] = vis[1] = 1;
    for (int i = 2; i < N; i++) {
        if (!vis[i]) primes.push_back(i);
        for (int p : primes) {
            if (i * p >= N) break;
            vis[i * p] = 1;
            if (i % p == 0) break;
        }
    }
}
int main() {
    int _;
    cin >> _;
    init();
    while (_--) {
        int n;
        cin >> n;
        int ans = 1;
        if (!vis[n]) {
            ans = 2;
        } else {
            vector<int> v;
            for (int p : primes) {
                if(n<p) break;
                if (n % p == 0) {
                    int c = 0;
                    while (n % p == 0) {
                        c++;
                        n /= p;
                    }
                    v.push_back(c);
                }
            }
            if (n > 1) v.push_back(2);
            // cout << v.size() << endl;
            if (v.size() == 1) ans = v[0] * 2;
            else {
                for (int c : v) ans *= (c + 1);
            }
        }
        cout << ans << endl;
    }
}