算法
(数论)
结论:
$f(x)$ 的最大操作次数是 $[1, n]$ 中的最大素数
可以先预处理出 $1 \sim 2e6$ 以内的所有素数,然后从 $n$ 开始倒着枚举当前数是否是素数
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
// linear sieve
vector<int> ps, pf;
void sieve(int mx) {
pf.resize(mx + 1);
rep(i, mx + 1) pf[i] = i;
for (int i = 2; i <= mx; ++i) {
if (pf[i] == i) ps.push_back(i);
for (int j = 0; j < ps.size() and ps[j] <= pf[i]; ++j) {
int x = ps[j] * i;
if (x > mx) break;
pf[x] = ps[j];
}
}
}
void solve() {
int n;
cin >> n;
if (n == 1) {
cout << "1\n";
return;
}
for (int i = n; i >= 2; --i) {
if (pf[i] == i) {
cout << i << '\n';
return;
}
}
}
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
sieve(2000000);
int t;
cin >> t;
while (t--) solve();
return 0;
}
我们洛谷这道题就是给入门组练手的