解题思路

如果我们直接模拟整个过程，会超时，因为 $k$ 太大。所以需要一些简单的观察：

• 如果 $n$ 是偶数，那么每次操作中 $n$ 都会加上 $2$，并且始终保持偶数。
• 如果 $n$ 是奇数，那么第一次操作会使 $n$ 加上一个奇数，之后 $n$ 变成偶数。

因此，很容易看出答案如下：

• 当 $n$ 是偶数时：

  $$n + 2k$$

• 当 $n$ 是奇数时：
  设 $d(n)$ 为 $n$ 的最小正因子（除了 $1$ 以外）。第一次操作后，$n$ 变为 $n + d(n)$，这是一个偶数。之后剩余的 $k-1$ 次操作，每次加上 $2$。因此：

  $$n + d(n) + 2(k - 1)$$

其中 $d(n)$ 可以在 $O(\sqrt{n})$ 时间内计算（实际实现中通常 $O(n)$ 预处理，但这里每个 $n$ 单独计算也很快）。

总复杂度为 $O(n)$。

#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;
}