题目
Description
WZK是个数学狂热爱好者。最近他又想出了一道题目来考大家。题目很简单，给定一个正整数n，对于所有不超过n的正整数，找到包含约数最多的一个数。如果有多个这样的数，那么回答最小的那个。
Input
输入一行一个正整数n，其中1 ≤ n ≤ 10^16。
Output
输出仅一行，一个满足上述条件的正整数。
Sample Input
100
Sample Output
60
Data Constraint
Hint
有30%的数据，n不超过1000。
有50%的数据，n不超过1000000。
有100%的数据，1 ≤ n ≤ 10^16
分析
先打个素数表，然后根据表打出跟多约数的数
代码
1 #include<bits/stdc++.h>
2 #define L long long
3 using namespace std;
4 L n,pi,ans,num;
5 int p[
10005];
6 bool flag[
1000010];
7 void fun()
8 {
9 for(
int i=
2;i<=
1000000;i++
)
10 if(!
flag[i])
11 {
12 p[++pi]=
i;
13 for(
int j=
2;j<=
1000000/i;j++
)
14 flag[j*i]=
1;
15 }
16 }
17 void dfs(L x,
int lev,
int t,
int s)
18 {
19 if(t>num||(t==num&&x<ans)) ans=x,num=
t;
20 int j=
0,l=
1,q;
21 L i=
x;
22 while(j<
s)
23 {
24 j++,l++
;
25 if(n/i<p[lev])
break;
26 q=t*
l;
27 i*=
p[lev];
28 if(i<=n) dfs(i,lev+
1,q,j);
29 }
30 }
31 int main()
32 {
33 fun();
34 cin>>
n;
35 dfs(
1,
1,
1,
30);
36 cout<<
ans;
37 }
转载于:https://www.cnblogs.com/zjzjzj/p/10698953.html
