牛客练习赛70 C.Mu函数

题目链接

题目描述

输入描述:

第一行一个正整数T表示数据组数

接下来T行每行两个数n,k

输出描述:

共T行每行一个答案

示例1

输入

2
1 1
3 2

输出

2
1

打表很容易发现存在循环节，而且循环节的长度非常小，所以对每组输入，找循环节即可，AC代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
ll prime[N],k;
bool isprime[N];
void Prime(){
    fill(isprime,isprime+N,1);
    k=0;
    for(int i=2;i<=N;i++)
    {
        if(isprime[i]) prime[k++]=i;
        for(int j=0;j<k;j++)
        {
            if(i*prime[j]>N) break;
            isprime[i*prime[j]]=0;
            if(i%prime[j]==0) break;
        }
    }
}

ll solve(ll n){
    if(n==1) return 1;
    ll cnt=0,sum=0;
    for(ll i=0;i<k&&prime[i]*prime[i]<=n;i++){
        if(n%prime[i]==0){
            cnt=0;
            while(n%prime[i]==0){
                cnt++;
                n/=prime[i];
            }
            if(cnt>1) return 0;
            else sum++;
        }
    }
    if(n>1) sum++;
    return sum%2?-1:1;
}

int main() {
    Prime();ll n,k;
    int t;scanf("%d",&t);
    while(t--){
        scanf("%lld%lld",&n,&k);
        map<ll,ll>m;
        ll s=-1,e,id=1;
        vector<ll>v1,v;
        while(1){//找循环节，v1存循环节之前的值，v存循环节内的值
            n=n+solve(n);
            m[n]++;
            if(m[n]==1){
                v1.push_back(n);
            }else if(m[n]==2){
                if(s==-1) s=id;
                v.push_back(n);
            }else if(m[n]==3){
                e=id-1;
                break;
            }
            id++;
        }
        if(k<=s-1) printf("%lld\n",v1[k-1]);
        else printf("%lld\n",v[(k-(s-1))%(e-s+1)==0?v.size()-1:(k-(s-1))%(e-s+1)-1]);
    }
    return 0;
}