因为 \(\varphi(x)\) 的值只与 \(x\) 的不同质因子有关,又因为 \(2^{31}\) 之内的数的质因子个数不超过 \(10\),所以容易枚举 \(10\) 个位置上填入的质因子打出朴素的暴力,简单剪枝后得到 \(20\) 分。
注意需要先判掉 \(x = n + 1\) 的情况。
考虑优化:因为 \(\varphi\) 的值只与质因子有关(而不是质因子幂次),所以不用重复填入质因子,得到 \(68\) 分。
此时 \(x\) 可以表示为不同质数的乘积,设为 \(x = p_1 p_2 p_3 \cdots p_m\),则
\[\begin{align*} \varphi(x) &= x \frac {p_1 - 1} {p_1} \frac {p_2 - 1} {p_2} \frac {p_3 - 1} {p_3} \cdots \frac {p_m - 1} {p_m} \\ &= (p_1 - 1) (p_2 - 1) (p_3 - 1) \cdots (p_m - 1) \\ \end{align*} \]即 \(\forall i \in [1, m]\),有 \((p_i - 1) \mid n\),用这个剪枝即可。
剪枝后,搜索实际上是枚举选 / 不选质因子,时间复杂度 \(O(2^{\omega(n)} \sqrt n)\)。
实际实现中可以筛出一定范围内的质数,达到 \(O(2^{\omega(n)})\) 的时间复杂度,本题筛到 \(2 \cdot 10^5\) 即可通过。
#include <iostream>
#define int long long
using namespace std;
const int lim = 2e5;
const int mxx = 1ll << 31;
bool vis[lim + 5];
int pr[lim + 5], tail;
int n;
static inline bool isprime(int x) {
for (int i = 2; i * i <= x; ++i)
if (x % i == 0)
return false;
return true;
}
int ans = mxx + 1;
static inline void dfs(int x, int ph, int las, int dep) {
if (ph > n)
return;
if (x >= ans)
return;
if (ph == n)
ans = x;
if (n % ph)
return;
if (dep < 10)
for (int i = 1; i < las; ++i)
dfs(x * pr[i], ph * (pr[i] - 1), i, dep + 1);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
for (int i = 2; i <= lim; ++i) {
if (!vis[i])
pr[++tail] = i;
for (int j = 1; j <= tail && i * pr[j] <= lim; ++j) {
vis[i * pr[j]] = true;
if (i % pr[j] == 0)
break;
}
}
cin >> n;
if (n == 1) {
cout << 1 << endl;
return 0;
}
if (isprime(n + 1)) {
cout << n + 1 << endl;
return 0;
}
dfs(1, 1, tail, 1);
if (ans > mxx)
cout << -1 << endl;
else
cout << ans << endl;
return 0;
}
标签:10,Phi,frac,cout,剪枝,int,题解,P4780,因子
From: https://www.cnblogs.com/bluewindde/p/18430024