bzoj 3643 Phi的反函数

4

5

题解

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 50000;
bool p[N + 10];
int x, pr[N + 10];
long long anss;
void init() {
for (int i = 2; i <= N; ++i) {
if (!p[i]) pr[++pr[0]] = i;
for (int j = 1; j <= pr[0] && i * pr[j] <= N; ++j) {
p[i * pr[j]] = 1;
if (i % pr[j] == 0) break;
}
}
}
int is_prime(long long x) {
int up = floor(sqrt(x));
for (int i = 2; i <= up; ++i)
if (x % i == 0) return 0;
return 1;
}
void dfs(int las, long long ans, long long sum) {
if (ans == 1) {
anss = min(anss, sum);
return;
}
if (ans > floor(sqrt(x)) && is_prime(ans + 1)) {
anss = min(anss, 1ll * sum * (ans + 1ll));
return;
}
for (int i = las + 1; i <= pr[0]; ++i) {
if (ans % (pr[i] - 1) == 0) {
int nans = ans / (pr[i] - 1);
long long nsum = 1ll * sum * pr[i];
dfs(i, nans, nsum);
while (nans % pr[i] == 0) {
nans /= pr[i];
nsum *= 1ll * pr[i];
dfs(i, nans, nsum);
}
}
if (pr[i] > ans) return;
}
}
main() {
init();
anss = 2147483648ll;
scanf("%d", &x);
dfs(0, x, 1);
if (anss <= 2147483647) printf("%d\n", anss);
else puts("-1");
}