Magic Divisor

0

0 votes
Problem
Given n,a divisor d for a number x is special if d divides x but d^n does not.

Example :
for n=2 x=18 ,6 and 9 are special divisors whereas 3 is not special (since 3^2 divides 18)

Let's say function SD(x,n)=total number of special divisors for number x given n.
We need to figure out the total sums the function over a range i.e. Given numbers p,q and n we need to figure out
SD(p,n)+SD(p+1,n)....+SD(p+q,n)

Constraints : 1<=p<=10^7 ,1<=q<=10^7,2<=n<=10
Example:
Input
32
1
2

Output
5

Explanation
Here p=32,q=1,n=2
So output=SD(32,2)+SD(33,2)
32 has 3 special divisors 4,8,16 (not 2 since 2^3 divides 32)
33 has 2 special divisors 3,11
Time Limit: 5
Memory Limit: 256
Source Limit:
Editor Image

?