jwvg0425 Problem Solving

수학에서 하도 자주 얻어맞아서, 이제 두드려 맞을 때마다 어디서 머리가 깨졌는지 적어놓기로 했다. 오늘은 https://codeforces.com/problemset/problem/757/E 이 문제를 풀다 막혔는데, 어느 정도 성질을 찾은 다음 그걸로 최적화하려고 한참 애쓰다 실패했다. 그리고 힌트를 좀 얻고 싶어서 breakun님에게 수학 찬스를 쓴 결과.. 어느 정도의 사전 지식이 필요하다는 것을 알게 됐다. 이 문제를 해결하기 위해 필요했던 multiplicative function에 관한 성질을 아래에 정리해둔다. 정의 어떤 양의 정수 $n$ 에 대해, $ab = n, gcd(a, b) =1$ 이라고 하자. 이런 모든 $a, b$에 대해 $f(n) = f(a)f(b)$ 가 성립할 경우 함수 $f..