https://vijos.org/p/1889

同BZOJ2440..，不过这题要求的是有因数因子的，所以莫比乌斯函数要稍微改一下

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #define N 200000 7 #define ll long long 8 int mul[N+10],mark[N+10],p[N+10]; 9 ll K;10 void init(){11     mul[1]=1;12     for (int i=2;i<=N;i++){13         if (!mark[i]){14             p[++p[0]]=i;15             mul[i]=1;16         }17         for (int j=1;j<=p[0]&&p[j]*i<=N;j++){18             mark[i*p[j]]=1;19             if (i%p[j]) mul[i*p[j]]=-mul[i];20             else{21                 mul[i*p[j]]=0;22                 break;23             }24         }25     }26 }27 ll cal(ll x){28     ll sum=0,t=sqrt(x);29     for (ll i=2;i<=t;i++){30         sum+=x/(i*i)*mul[i];31     }32     return sum;33 }34 int main(){35     scanf("%lld",&K);36     init();37     ll l=K,r=25505460948LL,ans=0;38     while (l<=r){39         ll mid=(l+r)>>1;40         if (cal(mid)>=K) ans=mid,r=mid-1;41         else l=mid+1;42     }43     printf("%lld\n",ans);44 }