Count of Arrays of Size N that can be Formed Starting With K Such that Every Element is Divisible by the Next Element

Problem

Given two positive integers K, and N, find the number of arrays of size N that can be formed, having K as the first element and every element except the last is divisible by the array's next element. Since the count can be huge, print the modulo 10⁹ + 7.

Input: Two integers N and K.

Output: An integer.

For example

1.
Input: N = 3, K = 25
Output: 5
Explanation:
There are 5 valid arrays of size 3 starting with 25 and satisfying the given condition:
{25, 25, 25}
{25, 25, 5}
{25, 5, 5}
{25, 5, 1}
{25, 1, 1}.

 
2.
Input: N = 2, K = 4
Output: 9
Explanation:
There are 3 valid arrays of size 2 starting with 4 and satisfying the given condition:
{4, 4}
{4, 2}
{4, 1}

 
3.
Input: N = 4, K = 5
Output: 4

Recommended: Try to solve it yourself before moving on to the solution.

Solution

Approach: The idea is to use Combinators. 

As given, the first element of the array must be K, and therefore to satisfy the condition that every element is divisible by the next element, the next element should be one of the factors of the K. We will find all the powers of prime factors of K and try to place them in the array such that every element is divisible by the next element.

Algorithm

1. Initialise a variable res to store the count of arrays formed. 
2. Initialise res as 1.
3. Find all powers of prime factors of K, and then do the following for each prime factor p:
   1. Let count be the number of times p occurs in the value K. 
   2. Therefore, the number of possible ways to keep one of the factors of p is given by  ^{(N + count - 1)}C_count.
   3. Multiply res by the value ^{(N + count - 1)}C_count.
4. Return result.

// C++ program for the above approach

#include <bits/stdc++.h> 
using namespace std;
 
int MOD = 1000000007;
 
// Function to find the value of x raised to the power y modulo MOD 
long modPower(long x, long y)
{
 
	// Stores the value of x^y 
	long r = 1, a = x; 

	// Iterate until y is positive
	while (y > 0) { 
		if ((y & 1) == 1) { 
			r = (r * a) % MOD; 
		}

 	a = (a * a) % MOD; 
	y /= 2; 
	}
 
	return r;
 
}

// Function to perform use Fermat's little theorem for Modular Multiplicative Inverse
long modInverse(long x) 
{
	return modPower(x, MOD - 2); 
}
 
// Modular division x / y, find the modular multiplicative inverse of y and multiply by x 
long modDivision(long p, long q)
{
	return (p * modInverse(q)) % MOD; 
}

// Function to find Binomial Coefficient C(n, k) in O(k) time 
long C(long n, int k)
{
	// Base Case
	if (k > n) {
		return 0; 
	}
 
	long p = 1, q = 1;
	for (int i = 1; i <= k; i++) {
	
 		// Update the value of p and q 
		q = (q * i) % MOD;
		p = (p * (n - i + 1)) % MOD;
 	}
	
	return modDivision(p, q);
}
 
// Function to find the count of arrays having K as the first element satisfying the given criteria 
int countArrays(int N, int K) 
{
	// Stores the resultant count of arrays
     long res = 1;

     // Find the factorization of K
     for (int p = 2; p <=  sqrt(K) ; p++) {
		int count = 0; 
		
		while (K % p == 0) {
			K /= p; 
			count++; 
		} 
		res = (res * C(N - 1 + count, count)) % MOD;
 
	} 
    if(K > 1){
	// N Be the last prime factor, for c = 1 -> C(N-1+1, 1) = N
          res = (K *res) % MOD;
	}

	return res; 
}

int main()
 
{ 
int N = 3, K = 5;
cout << countArrays(N, K);
return 0; 
}

Input: N = 3, K = 25

Output: 

5

Time Complexity: O(√n ).  

Space Complexity: O(1)

Also see, Euclid GCD Algorithm