Easy Problem

일단 https://hapby9921.tistory.com/entry/BOJ-16644-Easy-Problem 이 블로그를 참고했읍니다.

 

일단 xhudy's sieve 랑 

harmonic lemma 를 모르기 때문에 이것부터 공부를 하는게 ?? (공부완)

    for(int i = 1;i <= n; i=j+1) {

        j = n/(n/i);

        sum += ((n/i)/i) * (j-i+1);

    }

    ll rsum = 0;

    for(int i = 1; i <= n; i++) {

        rsum += (n/i)/i;

    }

 

아니 이 두개가 같다고 ?? 말이 안되네...

n/i 의 합을 구하는데, 여기에 f(n/i)이면 n/i 대신 넣어주고, 밖에 g(i) 가 더해지면 구간합 빼서 해주면 됨.

근데 n/i /i 이게 될 줄은 몰랐는데 이게 되네요... 뭔가 다른 느낌인데 돌려보니까 뭐가 됨.

 

그럼 10^18 가 n 이면 1~sqrt(n) 까지 돌리면 됨. sqrt 에서 한번 더 sqrt 한 만큼의 시간이 걸리긴 함. 아니 그럼 전처리 시간이 에반디

 

 

조화순열이 있을 떄 floor(조화순열) 이면 서로 다른 수의 값은 2floor(sqrt(n)) 개 이하임.

1 ~ n/s

 

 

 

 

일단 뫼비우스 함수와 관련된 메르텐스 함수를 살펴보자. 메르텐스 함수는 뫼비우스 함수의 부분합으로 이루어진 함수다.

M(n)=n∑i=1μ(i) 로 쓸 수 있음.

 

harmonic lemma 에 적용시킬 거니까 메르텐스 함수를 빠르게 구해보자.