[Lua] 백준 23832 서로소 그래프

사실 이 문제는 구현이 핵심이 아니라서 루아가 아닌 언어여도 상관없다. Lua 코드블럭을 제대로 사용할 수 있게 될 때까지는 루아 코드는 안 올릴 것 같다. Phi(2) + Phi(3) .... Phi(N)을 구하면 된다.

 

Jinhan814님 블로그를 보면 오일러 피 함수의 독특한 성질 + 조화수열 DP(?)를 이용해 푸셨다. 이해가 힘들어서 그냥 Euler's sieve를 사용했다. 누적합으로 O(2N)을 O(N)으로 만드는 간단한 최적화를 해줬다.

 

 

n=io.read("*n")
--Euler's sieve + Prefix sum
phisum={}
phisum[1]=0
for i=2,n do
    if phisum[i]==nil then
        for j=1,(n//i) do
            if phisum[i*j]==nil then
                phisum[i*j]=(i*j)
            end
            phisum[i*j]=phisum[i*j]//i
            phisum[i*j]=phisum[i*j]*(i-1)
        end
    end
    phisum[i]=phisum[i]+phisum[i-1]
end
io.write(phisum[n])