bzoj 3643 Phi的反函数
Description
Input
Output
Sample Input
4
Sample Output
5
题解
学长出的题%%%
转个学长的题解
这题用到了一个非常常用非常重要的性质:对于long long级别的数字,它不同的质因子个数非常小,最多不会超过15个。因为最小的十来个质数乘起来就已经变得很大了。这就说明我们可以用爆搜来搞这个东西。对于这道题来说我们知道一个数的phi就是一坨质数和一坨(质数-1)的乘积,那么我们的任务就是把这些东西构造出来。
枚举所有的prime,如果这个prime合法的话那么prime-1一定是给定的x的约数。如果x不能整除prime-1的话就根本不用考虑这个质数了,否则就开始考虑把prime这个东西构造到答案里面去。首先除掉一个prime-1,答案乘以一个prime;接下来就一个一个地除掉prime,然后每次都进去搜一次直到不能除了为止,这相当于枚举了这个质因数的次数。
然而还有一个问题就是对于那些很大的质数没法筛出来,这就要利用每个数大于$\sqrt x$的质因子只会有一个,并且这个质因子一定表现为prime-1的形式,那么每次就判断一下当前剩下的这个数+1是不是一个大质数,如果是大质数的话就记录答案并且不用继续往下搜了,因为再往下搜答案只会再变大。
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 49 50 51 52 53 54 55 |
#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"); } |