이 문제는 이전에 풀었던 BOJ 11689 GCD(n,k) = 1 의 강화버전인 문제이다. 문제에서 구하고자 하는 바와 기본적인 코드 구조는 거의 동일하다고 볼 수 있다.단지, 입력되는 숫자의 범위가 기존 10^12에서 10^18로 늘어났단 점만 제외하면 말이다. 이렇게 범위가 늘어남으로 인해 많은 것이 바뀌었다. 기존에 11689번 문제는 에라토스테네스의 체를 이용해서 소수의 리스트들을 뽑아낸 뒤 (10^6까지의 소수만 뽑으면 된다) 이를 직접 입력된 n에 대입해가면서 인수인지 아닌지를 구분해 낸 뒤, 이를 소인수 리스트에 저장해서 오일러 피 함수를 구하는 방식으로 진행됐다. 하지만 수의 범위가 10^18이 되면서, 에라토스테네스의 체를 사용하는 것이 불가능하게 되었다.에라토스테네스의 체는 10^6을 ..
