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

#include <iostream>
#include <vector>
# include<bits/stdc++.h>

using namespace std;

const int MAX = 200010;  // 最大值 2 * 10^5
int a[MAX];  // 存储每个数的质因数个数
int b[MAX];  // 存储每个数的因子个数 
// 预处理函数
void decompose(int x){
	int count = 0;
	int cnt = x;
	for(int i = 2 ;i*i<=x;i++)
	    while(x%i == 0) count++,x/=i;
	if(x>1) count++;
	a[cnt] = count;
} 

void yinzi(int x){
	for(int i = 1;i*i<=x ;i++){
		if(x%i==0){
			b[x]++;
			if( i != x/i){
				b[x]++;
			}
		}
	}
} 
void preprocess(){
	for(int i = 2;i<=MAX;i++){
		decompose(i);
	}
	for(int i = 2;i<=MAX;i++){
		yinzi(i);
	}
}
int main() {
    preprocess();  // 进行预处理

    int T;
    cin >> T;  // 读取查询的个数
    
    while (T--) {
    	int ans = 0;
        int x;
        cin >> x;  // 每次查询一个数 x
        ans = max(a[x]*2,b[x]);
        cout<<ans<<endl;
    }

    return 0;
}

个人思路就是 ，一个数的权值和 要么不拆 ，要不全拆成质数，因为任意一个数 可以拆成质因子相乘 ，而每一个质因子贡献度为2，于是我们可以先预处理一下一个数的因子数，和他拆成质因子相乘的 数量 比如说 60 可以拆成 2*2*3*5 那么就是4 ，每个贡献为2 所以就是4*2 但是 60本身的因子就是有12个 所以答案是12， 按照这个思路我们预处理一遍 然后直接查表就行，但是我不知道牛客会不会存全局表。如果不会存 则没必要打表了。。直接一个数一个数判断就可以了

#include <iostream>
#include <vector>
# include<bits/stdc++.h>

using namespace std;

const int MAX = 200010;  // 最大值 2 * 10^5
//int a[MAX];  // 存储每个数的质因数个数
//int b[MAX];  // 存储每个数的因子个数 
// 预处理函数
int decompose(int x){
	int count = 0;
	int cnt = x;
	for(int i = 2 ;i*i<=x;i++)
	    while(x%i == 0) count++,x/=i;
	if(x>1) count++;
	return count;
} 

int yinzi(int x){
	int count = 0;
	for(int i = 1;i*i<=x ;i++){
		if(x%i==0){
			count++;
			if( i != x/i){
				count++;
			}
		}
	}
	return count;
} 
void preprocess(){
	for(int i = 2;i<=MAX;i++){
		decompose(i);
	}
	for(int i = 2;i<=MAX;i++){
		yinzi(i);
	}
}
int main() {
    preprocess();  // 进行预处理

    int T;
    cin >> T;  // 读取查询的个数
    
    while (T--) {
    	int ans = 0;
        int x;
        cin >> x;  // 每次查询一个数 x
      //  cout<<decompose(2)<<endl;
      //  cout<<yinzi(2)<<endl;
        ans = max(decompose(x)*2,yinzi(x));
        cout<<ans<<endl;
    }

    return 0;
}