C++14(g++5.4) 解法, 执行用时: 447ms, 内存消耗: 53564K, 提交时间: 2020-09-26 17:42:02

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7+7;
int u[N];
bool vis[N];
vector<int >prime;

void init(){
	u[1]=1;
    for(int i=2;i<N;i++){
    	if(vis[i]==0) u[i]=-1,prime.push_back(i);
    	for(int j=0;j<prime.size()&&i*prime[j]<N;j++){
    		vis[i*prime[j]]=1;
    		if(i%prime[j]==0) break;
			else u[i*prime[j]]=-u[i];
		}
	}
}

int main(){
	init();
	int t;
	cin>>t;
	while(t--){
		ll n; cin>>n;
		ll k; cin>>k;		
		while(u[n]!=0 && k){
			if(u[n]*u[u[n]+n]==-1) k%=2; 
			if(k)n=u[n]+n,k--;
		}
		cout<<n<<endl;
	}
} 

C++11(clang++ 3.9) 解法, 执行用时: 173ms, 内存消耗: 52648K, 提交时间: 2020-09-28 09:01:14

#include<bits/stdc++.h>
#define end 10000000
using namespace std;
const int nx=1e7+5;
int u[nx]={0,1},p[nx],tot;
bool np[nx];
int main(){
	for(int i=2;i<=end;++i){
		if(!np[i])p[tot++]=i,u[i]=-1;
		for(int j=0;j<tot&&1ll*i*p[j]<=end;++j){
			np[i*p[j]]=1;
			if(i%p[j]==0)break;
			else u[i*p[j]]=-u[i];
		}
	}
	int t;scanf("%d",&t);
	int n;long long k;
	while(t--){
		scanf("%d%lld",&n,&k);
		while(u[n]&&k){
			if(u[n]*u[n+u[n]]==-1)k%=2;
			if(k)n+=u[n],--k;
		}
		printf("%d\n",n);
	}
	return 0;
}