Mad Scientist

Introduction

Given two positive integers $n$ and $k$, find the biggest integer $i$ such that $k^{i}$ divides $n!$. Note that we are given the following bounds: $(2 ≤ n ≤ 1018, 2 ≤ k ≤ 1012)$.

Solutions

Idea

The main idea is to take advantage of unique prime factorization to write $k=p_{1}^{\alpha_{1}} ... p_{n}^{\alpha_{n}}$. After explicitly computing this factorization, the task is just to find the $p_{j}^{\alpha_{j}}$ which appears in $n!$ the least number of times $i$, and this $i$ will be the answer. To do this, it clearly suffices to compute the number of times $p_{i}$ appears in $n!$. To do this, we can just be careful about how we count. In other words, we do not have to explicitly compute $n!$ or its prime factorization. The rest of this section will deal with this counting.\\

Let $S$ be the number of times a given prime $p$ appears in $n!$, and let $l$ be the largest $l$ such that $p^{l}\le n$. Then I claim that \[ S = \sum_{i=1}^{l} \lfloor \frac{n}{p^{i}} \rfloor \] To see this, let $n_{i}$ be the number of integers $m \le n$ such that $i$ is the highest power of $p$ dividing $m$. Then \[ S = \sum_{i=1}^{l}in_{i} = n_{1} + n_{2} + n_{2} + \dots + n_{l} + \dots + n_{l} = \sum_{i=1}^{l}\sum_{k=i}^{l}n_{k} = \sum_{i=1}^{l}\lfloor \frac{n}{p^{i}} \rfloor \]

Now that we know how to compute $S_{j}$ for each prime $p_{j}$, it is easy to compute $i$ by taking \[ i = \min_{j} \lfloor \frac{S_{j}}{\alpha_{j}} \rfloor \]

Runtime

Prime factorization can be done in $\sqrt{k}$, and computing $S$ takes $log_{p_{j}} n$ time for each $p_{j}$. An extremely rough upper bound on $j$ is $\sqrt{k}$, so that the overall runtime is bounded roughly by $\sqrt{k} log n$.

Code

Solution - Java

import java.util.ArrayList;
import java.util.Scanner;

public class DividingPowers {
	static Scanner in = new Scanner(System.in);

	public static void main(String[] args) {
		long caseNum=1;
			long a = in.nextLong();
			for(long i = 0; i<a; i++){
				long n = in.nextLong();
				long k = in.nextLong();
				long ans = largestPower(n,k);
				System.out.printf("%d\n", ans);
				caseNum++;
			}
	}
	public static long largestPower(long n, long k){
		ArrayList<Long> primes = primeFactorization(k);
		long minAppearance = Long.MAX_VALUE;
		for(int i = 0; i <(primes.size()+1)/2; i++){
			long p = primes.get(i*2);
			long temp = numAppearances(n,p);
			if(minAppearance> temp/primes.get(i*2+1)){
				minAppearance = temp/primes.get(i*2+1);
			}
		}
		return minAppearance;
	}
	private static long numAppearances(long n, Long p) {
		long numAppear=0;
		int i = 0;
		while(Math.pow(p, i)<=n){
			i++;
		}
		i--;
		for(int j = 1; j<=i; j++){
			numAppear+=n/((long)Math.pow(p, j));
		}
		return numAppear;
	}
	
	private static ArrayList<Long> primeFactorization(long k) {
		ArrayList<Long> primes = new ArrayList<Long>();
		for(long i = 2; i<=Math.sqrt(k); i++){
			long j = 0;
			while(k%((long)Math.pow(i, j))==0){
				j++;
			}
			if(j>1){
				primes.add(i);
				primes.add(j-1);
				ArrayList<Long> restPrimes = primeFactorization((long)(k/(Math.pow(i, j-1))));
				i=k;
				for(Long a : restPrimes){
					primes.add(a);
				}
			}
			
			
		}
		if(primes.size()==0&&k!=1){
			primes.add(k);
			primes.add((long) 1);
		}
		return primes;
	}
	
	

}