CS - 뫼비우스 함수 - Answer Code

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#define MAX_SQRT 50000
using namespace std;
typedef long long int lli;


int mu[MAX_SQRT+1];
vector<int> primes;
bool isPrime[MAX_SQRT+1];
void mobius_seive() {
    fill(isPrime, isPrime + MAX_SQRT + 1, true);
    isPrime[0] = false;
    isPrime[1] = false;
    mu[1] = 1;
    for(int i = 2;i<=MAX_SQRT;++i) {
        if(isPrime[i]) {
            primes.push_back(i);
            mu[i] = -1;
        }
        for(int p:primes) {
            if (i*p>MAX_SQRT) {
                break;
            }
            isPrime[i*p] = false;
            if(i%p==0) {
                mu[i*p] = 0;
                break;
            } else {
                mu[i*p] = -mu[i];
            }
            
        }
    }
}

lli countSquareFree(lli n) {
    lli count = 0;
    lli limit = (lli)sqrt(n);
    for(lli d = 1;d <= limit;++d) {
        count += (lli)(mu[d] * (n/(d*d)));
    }
    return count;
}

int main(void) {
    lli n = 0;
    scanf("%lld", &n);
    mobius_seive();
    lli low = 1;
    lli high = 2000000000;
    lli ans = high;
    while(low <= high) {
        lli mid = (low + high) / 2;
        lli tmp = countSquareFree(mid);
        if(tmp >= n) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    printf("%lld", ans);
}