定义 \(f(x)\) 为 \(x\) 的 \(> 1\) 的最小因子。
给一个正整数 \(n\ (n \geq 2)\) 。对它执行 \(k\) 次操作:每次让 \(n = n + f(n)\) 。询问 \(k\) 次操作后 \(n\) 的值。
在唯一分解定理下观察 \(n\) :偶数的最小非 \(1\) 因子一定是 \(2\) ,奇数的最小非 \(1\) 因子一定是奇数。
则有:
- 若 \(n\) 是偶数,则 \(k\) 次操作后 \(n = n + 2k\) 。
- 若 \(n\) 是奇数,则 \(k\) 次操作后 \(n = n + f(n) + 2(k - 1)\) 。
view
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
int n, k; std::cin >> n >> k;
if (~n & 1) std::cout << n + 2 * k << '\n';
else {
int p = n;
for (int i = 2; i * i <= n; i++) { // 枚举除 (1, p) 外,p 的所有因子对
if (n % i) continue;
p = i;
break;
}
std::cout << n + p + 2 * (k - 1) << '\n';
}
}
int main() {
int _ = 1; std::cin >> _;
while (_--) {solve();}
return 0;
}