테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 정확해 ======

===== 풀이 =====
  * 번역이 살짝 헷갈린다. 제대로 다시 정리하면, K<M이고, K∣M 이고, K^N∤M 의 세 조건을 모두 만족하면 K는 M의 멋진 약수이다.
  * f(X) = d(1) + d(2) + ... d(X)을 계산하면, 최종 답은 f(A+B) - f(A-1)로 구할 수 있다.
  * f(X)는 1~X 까지의 모든 수의 약수의 갯수의 합을 먼저 구하고, 약수이지만 멋진 약수가 아닌 수의 갯수를 빼주면 된다.
  * 모든 수의 약수의 갯수의 합은 [[ps:정수론적 함수#f_1_f_2__f_n_을_계산|∑f(x) 계산]]에 설명된 방식으로 O(sqrt(X))에 계산 가능
  * 약수이지만 멋진 약수가 아닌 수의 갯수의 합은, 
    * K^N∤M 을 만족하지 않는 약수의 갯수의 합 = 모든 1~X까지의 K에 대해서 K^N 을 약수로 갖는 M의 갯수의 합 = [X/(1^N)] + [X/(2^N)] + [X/(X^N)]
      * K^N ≤ X일때까지만 계산하면 되니까 실질적으로 계산해야할 텀의 갯수는 O(X^(1/N))개라서 일일이 계산해도 O(X^(1/N))에 해결된다
    * K<M을 만족하지 않는 약수의 갯수의 합 = X개
    * 두가지를 동시에 만족하는 약수의 갯수 = 1개 (X=1일때, K=1)
  * 따라서 f(X) = ∑τ(x) - (X/(1^N)] + [X/(2^N)] + [X/(X^N)]) - X + 1 로 O(sqrt(X))에 계산 가능하다.
  * 최종 답인 f(A+B) - f(A-1) 를 계산하는 것도 O(sqrt(A+B))로 계산되다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1457. 정확해".

- Problem link: https://www.acmicpc.net/problem/1457
- Solution link: http://www.teferi.net/ps/problems/boj/1457
"""

import math


def sigma_d(num, exp):
    if num == 0:
        return 0
    sqrt = math.isqrt(num)
    answer = 2 * sum(num // i for i in range(1, sqrt + 1)) - sqrt * sqrt
    i = 1
    while (x := i**exp) <= num:
        answer -= num // x
        i += 1
    answer -= num - 1
    return answer


def main():
    A, B, N = [int(x) for x in input().split()]
    print(sigma_d(A + B, N) - sigma_d(A - 1, N))


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_1}}