Trick : 1 0 x 10^x 10x 以内最多的因子数
-
1 0 5 10^5 105 以内具有最多的因子数的数是 83160,它有 128 个因子 ;
-
1 0 6 10^6 106 以内具有最多因子数的数是 720720,它有 240 个因子 ;
所以遇到需要枚举因子的,预处理之后大胆枚举就可以, 时间复杂度很低
计算因子数代码如下 :
int cal(int x){
unordered_set<int> st;
for(int i = 1; i <= x / i; i ++){
if(x % i == 0){
st.insert(i);
st.insert(x / i);
}
}
return st.size();
}
void solve(){
int num = -1, mx = -1;
for(int i = 1; i <= 1e6; i ++){
if(cal(i) > mx){
mx = cal(i);
num = i;
}
}
cout << num << ' ' << mx << '\n';
}