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

唯一分解定理:任何一个大于1的整数n都可以分解成若干个质数的连乘积

那么 $x = a_{1}^{p_{1}} \times a_{2}^{p_{2}} \times ... a_{k}^{p_{k}} \times ... a_{n}^{p_{n}}$

则 $x$ 的因子总个数为 $(p_{1} + 1) \times (p_{2}+1) \times ... (p_{k} +1)\times ...( p_{n}+1)$

那么对于给定的n，求 $\sum_{i = 1}^{k}{wt(p_{i})}$

方案一：全部分解为质数，那么值为 $2 \times (p_{1}+ p_{2} + ... + p_{k} + ... p_{n})$

方案二：不分解，那么值为 $(p_{1} + 1) \times (p_{2}+1) \times ... (p_{k} +1)\times ...( p_{n}+1)$

方案三：分解部分：例如将n分解为: $x_{1} = a_{1}^{p1} \times a_{2}^{p_{2}}, x_{2} = a_{3}^{p_{3}} \times ... a_{k}^{p_{k}} \times ... a_{n}^{p_{k}}$ ,那么值为 $(p_{1} + 1) \times (p_{2} + 1) + (p_{3} + 1) \times (p_{4} + 1) \times ... \times (p_{n} + 1)$

显然方案二总是比方案三更好，所以只需考虑方案一与方案二的优劣

当n只能分解为一个质数时，此时方案一的值为 $2 \times p_{1}$ ，而方案二为 $(p_{1} + 1)$ ,此时方案一比方案二更优

当n可以分解为多个质数时，方案二比方案一更优

总代码：

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


void solve(){
    int x; cin >> x;
    vector<int> a;
    for(int i = 2; i * i <= x; i ++){
        if(x % i == 0){
            int cnt = 0;
            while(x % i == 0) cnt ++, x /= i;
            a.push_back(cnt);
        }
    }
    if(x > 1) a.push_back(1);
    if(a.size() == 1) cout << 2 * a[0] << endl;
    else{
        int sum = 1;
        for(int e : a) sum = sum * (e + 1);
        cout << sum << endl;
    } 
    return ;
}
signed main(){
    HelloWorld;
    
    int tt; cin >> tt;
    while(tt --) solve();
    return 0;
}