1457번 - 정확해

0보다 큰 정수 K가 M보다 작은 약수이지만, M이 K^N으로 나누어 떨어지지 않을 때, K를 M의 멋진 약수라고 한다. d(M)을 M의 멋진 약수의 개수라고 했을 때, d(A) + d(A+1) + ... + d(A+B)를 구하는 프로그램을 작성하시오.

첫째 줄에 세 개의 정수 A, B, N이 주어진다.

첫째 줄에 답을 출력한다. 정답은 항상 2147483647보다 작거나 같다.

• 1 ≤ A ≤ 10⁶
• 1 ≤ B ≤ 10⁷
• 2 ≤ N ≤ 10