[중고딩문제] 2024 china tst day1 p3

[익명(1.229)]

형들 2번째 사진 뫼비우스 반전 공식 수식 왜 합 함수가 {n/d}가 되는거야? 이거 풀이 올린애가 자명하다는데 모르겠어.

[Solidus(liquidsolidus)]

beta가 뫼비우스 반전에 의해 sum_{d | M} u(d)/d가 된다는 건 잘 알고 있을 거임 이제 h(n) = (n 이하의 자연수 중 M과 서로소인 것의 개수) = sum_{k=1..n} (서로소일 때 1, 아닐 때 0) 을 뫼비우스 반전 꼴로 표현해야 하는데 저 지시함수는sum_{k=1..n} sum_{d | gcd(k, M)} u(d)형태로 바꿔서 이중 시그마로 표현 가능하고 d는 k, M의 약수니까 아래처럼 시그마끼리 순서를 바꿀 수 있으니 sum_{d | M} sum_{k=1..n, d | k} u(d) = sum_{d | M} (u(d) * sum_{k=1..n, d | k} 1) = sum_{d | M} u(d) * floor(n/d)로 변형 가능함

[Solidus(liquidsolidus)]

넹 정수론에서 이 기법은 자주 나와용

[익명(1.229)]

형 고마워 근데 내가 이해한게 맞나 확인하고 싶은데 지시함수를 뫼비우스 반전꼴로 표현할때 두번째 시그마 함수를 뫼비우스 함수의 합으로 한게 전부 합해도 1이니까 원래 지시함수 식이랑 같으니까 저렇게 바꾼거지?

[수갤러 1(49.174)]

이건 정수론 문제인가요?