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^{9} + 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
 Initialise a variable res to store the count of arrays formed.
 Initialise res as 1.

Find all powers of prime factors of K, and then do the following for each prime factor p:
 Let count be the number of times p occurs in the value K.
 Therefore, the number of possible ways to keep one of the factors of p is given by ^{(N + count  1)}C_{count.}
 Multiply res by the value ^{(N + count  1)}C_{count.}
 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(N1+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