时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
Given an integer n, for all integers not larger than n, find the integer with the most divisors. If there is more than one integer with the same number of divisors, print the minimum one.
输入
One line with an integer n.
For 30% of the data, n ≤ 103
For 100% of the data, n ≤ 1016
输出
One line with an integer that is the answer.
- 样例输入
-
100
- 样例输出
-
60
_______________________________________
Solution:
将正整数n进行质因数分解：
n = p1^k1 * p2^k2 * ... * pm^km
(p1 < p2 < ... < pm)
易见,n的因子数为
(1+k1)*(1+k2)*...*(1+km)
接下来考虑不超过N的正整数中，因子数最多且最小的数,记为s(N)。
我们可以推导出s(N)的质因数分解的形式有下列特征：
（1） s(N) = 2^k1 * 3^k2 * 5^k3 * ...* p[i]^ki * ... *p[m]^km
式中p[i]表示第i个质数。
（2） k1 <= K2 <= k3 <= ... <=km
可概括为：
(1)质因子连续
（2）指数单调不增
因此可采取暴力搜索（DFS）的办法求解。
————————————————————————————————————
Complexity:
前14个质数的乘积为 13082761331670030 ~ 1.3E16
所以搜索层数最多为13层，复杂度可大胆估计为2^13，这里不需要估计得比较准确。
————————————————————————————————————————————————————————————
Implementation:#include <bits/stdc++.h>
using namespace std;
typedef long long LL; const int N();
bool p[N];
int P[N];
int np; void seive(int n){
memset(p, , sizeof(p));
p[]=p[]=;
for(int i=; i<=n; i++){
if(p[i]) P[np++]=i;
for(int j=i<<; j<=n; j+=i)
p[j]=;
}
} LL ans, val, n; void dfs(int lev, LL res, int cnt, LL v){
if(v*P[lev]>n){
if(res>ans){
ans=res;
val=v;
}
else if(res==ans&&val>v)
val=v;
}
else{
for(int i=; v*P[lev]<=n&&i<=cnt; i++){
v*=P[lev];
dfs(lev+, res*(i+), i, v);
}
}
} int main(){
seive();
cin>>n;
val=n;
dfs(, , , );
cout<<val<<endl;
}