1~n까지 소인수분해 다 해서 각 n의 약수들, phi(n) 같은거 미리 다 뽑아놓은 다음,

이제 어떤 자연수 r이랑 r의 약수들 r1, r2, ... , rk들에 대해, {gcd(1,r-1), gcd(2,r-2), ..... }가 {r1이 phi(r/r1)개, r2가 phi(r/r2)개, ... rk가 phi(r/rk)개} 라는걸 써먹으면 n log n 나오는것 같긴 합니다. 아쉽게도 전 구현하다 시간 다 되서 못풀었네요.