I know it’s not a correct way of solving this question.
I’m expecting TLE but getting wrong answer.
My approach : Let’s assume value of N is 8 and k is 2.
8! = 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
Now we can run a loop from i=k to i<=n and ( i += k) add the powers for each i.
Illustration :
x =0
i = 2 // x = 1 ( 0 + 1 )
i = 4 // x = 3 ( 1 + 2 )
i = 6 // x = 4 ( 3 + 1 )
i = 8 // x = 7 ( 4 + 3)
Here is my code
import java.util.*;
public class Main {
static int get_powers(int n, int k)
{
int p=0;
while( n%k == 0)
{
n /=k;
p++;
}
return p;
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int t= sc.nextInt();
int n,k;
long x;
while(t-- > 0)
{
n = sc.nextInt();
k = sc.nextInt();
x =0;
for(int i=k; i<=n; i+=k)
{
x += get_powers(i,k);
// System.out.println(i+" * "+k);
}
System.out.println(x);
}
}
}