Count Arrays with Fixed Product

Find the number of arrays of length $L$ containing positive integers whose product is equal to $P$.

$L\le {10}^5$ and $P\le {10}^{10}$

This is a subproblem of ABC370G: Divisible by 3. You can submit it here

First, let’s solve an easy version. Assume $P=p_1^{{\alpha }_1}$

We should have $a_1\cdot a_2\dots a_L=p_1^{{\alpha }_1}$. It is clear that each $a_i$ can have only have $p_1$ as its prime factor, although the multiplicity of the exponent might differ. However, their product should contain exactly ${\alpha }_1$ multiplicity.

So, let’s assume that $a_i=p_1^{x_i}$. Then, we should have $$p_1^{x_1}\cdot p_1^{x_2}\dots p_1^{x_L}=p_1^{{\alpha }_1}$$ So we are looking for the number of non-negative solution to: $$x_1+x_2+\cdots +x_L={\alpha }_1$$

From Stars and Bars, the number of distinct solution is equal to $(\genfrac{}{}{0ex}{}{L+{\alpha }_1-1}{{\alpha }_1})$. If you are not familiar with Stars and Bars, you can read about it here but don’t read too much into it, else you’d end up confusing yourself. For a long time, I was afraid of problems that involved Stars and Bars, mainly because I used to apply Stars and Bars combinatorics from scratch for each problem.

But if you take the combinatorics for granted, and just memorize the formula for $$x_1+x_2+\cdots +x_n=sum$$ is $(\genfrac{}{}{0ex}{}{n+sum-1}{sum})$, you will be able to solve all problems that involve Stars and Bars. Why? Because there’s a bijection between them, and every problem that can be solved using Stars and Bars can also be reduced to counting the number of distinct integral solution of a given equation. This abstraction is extremely useful for solving Combinatorial problems.

What if $P$ had 2 different prime factors? Suppose $P=p_1^{{\alpha }_1}\cdot p_2^{{\alpha }_2}$. Since $a_1\cdot a_2\dots a_L=p_1^{{\alpha }_1}\cdot p_2^{{\alpha }_2}$, it is clear that each $a_i$ will have atmost 2 prime factors, i.e, $p_1$ and $p_2$.

Assume $a_i=p_1^{x_i}\cdot p_2^{y_i}$. Then $$(p_1^{x_1}\cdot p_1^{x_2}\dots p_1^{x_L})\cdot (p_2^{y_1}\cdot p_2^{y_2}\dots p_2^{y_L})=p_1^{{\alpha }_1}\cdot p_2^{{\alpha }_2}$$ So we are looking for the number of non-negative solution to $$x_1+x_2+\cdots +x_L={\alpha }_1$$ $$y_1+y_2+\cdots +y_L={\alpha }_2$$

Notice that all $x_i$ are correlated to each other, all $y_i$ are correlated to each other (because their sum is fixed). However, $x_i$ does not interact with $y_j$. Hence, they are independent. So the total number of ways is equal to the product of the number of ways to find $X=(x_1,x_2,\dots ,x_L)$ and $Y=(y_1,y_2,\dots ,y_L)$, which is nothing but $$(\genfrac{}{}{0ex}{}{L+{\alpha }_1-1}{{\alpha }_1})\cdot (\genfrac{}{}{0ex}{}{L+{\alpha }_2-1}{{\alpha }_2})$$

What if $P=p_1^{{\alpha }_1}\cdot p_2^{{\alpha }_2}\dots p_k^{{\alpha }_k}$? Note that the prime factors do not interact with each other. Therefore, the number of distinct arrays with product $P$ is equal to $$\prod _{i=1}^k(\genfrac{}{}{0ex}{}{L+{\alpha }_i-1}{{\alpha }_i})$$

Since $N\le {10}^{10}$, you can compute prime factorization in $O(\sqrt{n})$. Notice that each ${\alpha }_i$ cannot be bigger than $\log (N)$. Why?

Therefore, factorials can be precomputed to compute $(\genfrac{}{}{0ex}{}{N}{R})$ fast.

You can submit this problem here.

Code

Suppose $$f(N)=\prod _{i=1}^k(\genfrac{}{}{0ex}{}{L+{\alpha }_i-1}{{\alpha }_i})$$ and $$f(M)=\prod _{i=1}^{k^{\prime }}(\genfrac{}{}{0ex}{}{L+{\beta }_i-1}{{\beta }_i})$$

If $N$ and $M$ are co-prime, notice that $$f(N\cdot M)=f(N)\cdot f(M)$$

This is because the prime factorization of co-prime integers have nothing in common, therefore, the product will contain all prime factors in each number. Hence, none of the primes interacts with each other, even in the multiplication.

Functions that obey this property for co-prime inputs are known as Multiplicative Functions.

How do you find out the number of arrays of length $L$ with product $\le N$?

We are simply looking for $$f(1)+f(2)+f(3)\cdots +f(N)$$

Naively computing it would lead to TLE, as $N\le {10}^{10}$.

However, since this is a multiplicative function, there exists a dynamic programming solution to compute the prefix sum of multiplicative functions efficiently. I might add another blog on this topic in future, but feel free to google the keyword and do your own research.

This technique is needed to gain full points for ABC370G: Divisible by 3.

If you liked the contents of this blog, you might like problem How many arrays from Codechef.