写题看看数据范围啊~
相关题目:[BZOJ3643]Phi的反函数

Description

Sample Input

4

Sample Output

5

Source

By Zky

Solution

设目标值为 xx

所以 xx 至多有 1010 个质数。 而显然每个质数最多只有 3030 次方。

暴搜+剪枝即可。

Code

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
41
42
43
44
45
46
47
48
#include <iostream>
#include <climits>
#include <algorithm>
#include <cmath>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
typedef long long ll;
int n, base;
int p[25000], vis[46341];
inline void init(const int N) {
int t;
rep(i,2,N) {
if(!vis[i]) p[++*p]=i;
for(int j=1;j<=*p&&(t=i*p[j])<=N;++j) {
vis[t] = 1;
if(i%p[j]==0) break;
}
}
}
long long ans=~0U>>1;
bool isprime(int x) {
for(int z=2;z*z<=x;++z)
if(x%z==0) return 0;
return 1;
}
void dfs(int k, long long now, int res) {
if(res==1) { ans=min(ans,now);return;}
if(res>base && isprime(res+1)) {ans=min(ans,now*(res+1));return;}

rep(i,k,*p)if(res%(p[i]-1)==0) {
ll nnow=now*p[i]; int rres=res/(p[i]-1);
dfs(i+1, nnow, rres);
while(rres%p[i]==0) {
rres/=p[i], nnow*=p[i];
dfs(i+1, nnow, rres);
}
}
}

int main() {
cin >> n; base=(int)sqrt(n);
init(46340);
dfs(1,1,n);
if(ans==~0U>>1) puts("-1");
else cout << ans << endl;
return 0;
}