Ordered Prime Factorizations
National Olympiad — National round
Submission name: decomposition.cpp
Problem summary
Factor N into primes and count distinct sequences of those prime factors. Only their order varies; equal prime factors are indistinguishable.
Input
Integer N.
Output
The exact count.
Constraints
2 ≤ N ≤ 1000000000.
Worked example
An independently prepared example for this explanation.
Input
18
Output
3
Solution analysis
- Trial-divide N to obtain the multiplicity of each prime.
- If t factors have already been placed and the next prime occurs e times, choose its e positions among t+e. Multiply by that binomial coefficient.
- Build a small Pascal triangle so factorial overflow is avoided.
Why it works
Choosing positions for each group of identical primes gives the multinomial coefficient (sum e)!/product(e!).
Complexity: O(sqrt(N)+log²N) time; O(log²N) space.
Watch out. Factorials can overflow even when the final answer fits; binomial multiplication avoids unnecessary factorial intermediates.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Choosing positions for each group of identical primes gives the multinomial coefficient
// (sum e)!/product(e!).
#include<iostream>
#include<vector>
using namespace std;
int main(){
long long n;
cin>>n;
vector<int>e;
for(long long p=2;p*p<=n;p++){
if(n%p){
continue;
}
int k=0;
while(n%p==0){
n/=p;
k++;
}
e.push_back(k);
}
if(n>1){
e.push_back(1);
}
long long c[31][31]={};
for(int i=0;i<=30;i++){
c[i][0]=c[i][i]=1;
for(int j=1;j<i;j++){
c[i][j]=c[i-1][j-1]+c[i-1][j];
}
}
long long ans=1;
int t=0;
for(int k:e){
ans*=c[t+k][k];
t+=k;
}
cout<<ans<<'\n';
}