Three unordered factors
National Olympiad — Municipal round
Submission name: mult.cpp
Problem summary
Count unordered triples of positive integers whose product is n. Reordering the same factors does not create another representation.
Input
n.
Output
The number of representations.
Constraints
1≤n<10000000.
Worked example
An independently prepared example for this explanation.
Input
24
Output
6
Solution analysis
- Enumerate the smallest factor a while a³≤n.
- When a divides n, enumerate b from a while b²≤n/a. Count b when it divides n/a; the remaining factor c is determined.
Why it works
Every unordered triple has a unique sorted form a≤b≤c. The bounds and divisibility tests enumerate exactly these forms.
Complexity: O(n^(2/3)) time as a simple upper bound; O(1) space.
Watch out. Include factors equal to 1 and equal factors.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every unordered triple has a unique sorted form a≤b≤c. The bounds and divisibility tests
// enumerate exactly these forms.
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
long long n,ans=0;
cin>>n;
for(long long a=1;a*a*a<=n;a++){
if(n%a==0){
for(long long b=a;b*b<=n/a;b++){
if((n/a)%b==0){
++ans;
}
}
}
}
cout<<ans<<'\n';
}