Codeforces Round #641 Div2.A Orac and Factors 中文题解
Caro23333
2020-04-30 00:09:37
### Orac and Factors 中文题解
直接模拟是不可行的，因为操作次数太多。但我们不难发现对于任意的偶数 $n$ ，每次被操作会 $+2$ ，操作后仍是偶数；对于任意奇数 $n$ ，第一次操作会被加上一个奇数，随后变成一个偶数。所以答案为：
$$
\left\{
\begin{array}{lcl}
n+2k & n\textrm{ is even}\\
n+2(k-1)+d(n) & n\textrm{ is odd}\\
\end{array}
\right.
$$
其中 $d(n)$ 代表 $n$ 除 $1$ 以外的最小正因子，可以 $O(n)$ 枚举求得。
总复杂度 $O(\sum n)$ 。
Problem and Tutorial by Caro23333
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int main()
{
int T;
cin >> T;
while(T--)
{
int n,k;
cin >> n >> k;
if(n%2==0)
{
cout << n+2*k << endl;
continue;
}
int p = 0;
for(int i = n; i>=2; i--)
if(n%i==0)
p = i;
cout << n+p+2*(k-1) << endl;
}
return 0;
}
```