CodeForces 27E 素数筛,暴力

Posted by Cww97 on 2016-08-13

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/52196977
http://codeforces.com/problemset/problem/27/E

题意
给定一个正整数n,求一个最小的正整数,使得它的因子个数恰为n。保证答案不超过10^18

大家应该都知道质因数分解这玩意:
任意数字可以分解成x=p[1]^a[1]p[2]a[2]……p[k]a[k]
此事x的因子个数等于π(a[i]+1)(连乘)
(有证明不过链接我找不到了)
既然题目要因子数为n,要求最小
那我们显然可以从最小的素数开始找
接下来,,,就是素数之间不停的乘的暴力dfs了
注意if (num>=ans/p[dep])break;
这行一个剪枝,num
p[dep]已经无法更新ans了,后面搜到的不管有没有n个,都比ans大,必然是无效的,改成除法防爆
好气啊,一开始INF设置的小了只有4个3f,WA了两发

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N=507;
ll n,ans,p[107],P;

void getPrime(){
P=0;
bool isPrime[N];
memset(isPrime,1,sizeof(isPrime));
for(int i=2;i<N;i++){
if(isPrime[i])p[++P]=i;
for(int j=1;j<=P&&p[j]*i<N;j++){
isPrime[i*p[j]]=0;
if(i%p[j]==0)break;
}
}
}

void dfs(ll num,ll dep,ll cnt){
if (cnt> n)return ;
if (cnt==n){ans=min(ans,num);return;}
for (int i=1;i<63;i++){
if (num>=ans/p[dep])break;
dfs(num*=p[dep],dep+1,cnt*(i+1));
}
}

int main(){
getPrime();
while (scanf("%d",&n)==1){
ans = INF;
dfs(1,1,1);
printf("%I64d\n",ans);
}
return 0;
}