정확한 약수
시간 제한2초메모리 제한128 MB
A부터 A+B까지 각 수마다 K^N이 그 수를 나누지 않는 진약수 K의 개수를 구해 모두 더하는 문제입니다.
문제
양의 정수 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^61 <= B <= 10^72 <= N <= 10