Mu函数

思路：
看到K这么大，我们知道这种题一般要先从找规律的角度尝试一下。
f(x)=x+Mu(x)，那么跟据Mu(x)，我们知道如果x的Mu(x)为0，不管经过多少次迭代，其结果都是0
如果Mu(x)不为0呢，通过对Mu(x)打表我们可以大胆猜测，在k很大的时候，要么x通过迭代到了Mu(x)=0的点，会产生-1，1的死循环。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e7+10;

int prime[MAXN], prime_tot;
bool prime_tag[MAXN];
int mu[MAXN];
void pre_calc(int lim) {
    mu[1] = 1;
    for(int i = 2; i <= lim; i++) {
        if(!prime_tag[i]) {
            prime[++prime_tot] = i;
            mu[i] = -1;
        }
        for(int j = 1; j <= prime_tot; j++) {
            if(i * prime[j] > lim) break;
            prime_tag[i * prime[j] ] = true;
            if(i % prime[j] == 0) {
                    mu[i * prime[j]] = 0;
                    break;
            } else {
                    mu[i * prime[j]] = -mu[i];
            }
        }
    }
}



signed main()
{
    pre_calc(MAXN);
    ios::sync_with_stdio(0);
    int T;
    cin >> T;
    while(T--)
    {
        int n, k;
        cin >> n >> k;
        int x = n;
        while(k){
            if(mu[x] == 0) break;
            if(mu[x] == -1 && mu[x-1] == 1){
                x-= (k&1ll); break;
            }
            x += mu[n];
            --k;
        }
        cout << x << endl;
    }
}