[일반] 수학 관련 갤에 물어보는 게 맞는 거 같아서 질문함 정수론

[익명(211.207)]

힌트 보니까 오일러 phi 함수 쓰라던데 어떻게 접근해야 될 지 감이 안 잡힘

구체적인 접근 방법 알려줄 사람

[익명(49.143)]

PS갤러리로

[pseudo(kimbabsa)]

임의의 k에 대해 0<phi(k)<k이니깐 phi를 i번 합성한 phi^i(m) = phi(phi(...phi(m)...))의 값이 어떤 i 이상부터는 1인점을 이용하면 풀릴거 같은데

[pseudo(kimbabsa)]

더 나아가서 m이 1이상의 홀수 일땐 phi(m)가 짝수가 되고 m이 짝수일땐 phi(m) <= m/2가 성립하니깐 phi(phi(m)) < m/2가 성립하므로 로그스케일복잡도로 풀수 있을 듯?

[pseudo(kimbabsa)]

아 로그수준으로는 안되겠다. phi가 O(n^(1/2))라서. 다만 2log(m)번 제곱한것만 확인해도 답은 구할 수 있을 것 같늠