Longest Sum-Product Magic Sequence
National Olympiad — Regional round (2010 season)
Submission name: mag.cpp
Problem summary
Find a longest sequence of at least two positive integers whose sum and product both equal n. Print it in nondecreasing order, or No if none exists.
Input
One integer n.
Output
The sorted sequence, or the exact word No.
Constraints
3 < n ≤ 100000.
Worked example
Input and output for the worked example discussed below.
Input
6
Output
1 2 3
Solution analysis
- Numbers equal to 1 do not change a product. First choose factors greater than 1 whose product is n, then add exactly n minus their sum copies of 1. The length is n−Σ(factor−1). Thus maximizing length means minimizing this last sum.
- Whenever a composite factor ab is replaced by a,b, with a,b≥2, its contribution ab−1 decreases to a+b−2, because (a−1)(b−1)≥1. Repeating this split reaches the prime factorization, which therefore gives a longest possible sequence.
- Trial-divide n, collecting prime factors with multiplicity and their sum. Output n−sum ones, followed by the already sorted factors. If n is prime there is only one factor and no added ones, so the required length exceeds neither one nor the rule: print No.
- For n=6 the prime factors are 2 and 3, whose sum is 5. Add one 1 to obtain [1,2,3], with sum and product 6. For n=13 no valid multi-element sequence exists.
Why it works
Splitting any composite factor cannot reduce the achievable length, so prime factors maximize it. Their product remains n; adding n−sum ones makes the sum n without changing the product. Composite n≥4 has prime-factor sum at most n and at least two factors. Prime n admits only one factor greater than 1 and cannot satisfy the minimum length.
Watch out. Do not omit repeated prime factors. Ones must precede primes in the output. A prime input must print No, not its one-element factorization.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n;
cin>>n;
int remaining=n;
int sum=0;
vector<int>factors;
for(int prime=2;prime*prime<=remaining;prime++){
while(remaining%prime==0){
factors.push_back(prime);
sum+=prime;
remaining/=prime;
}
}
if(remaining>1){
factors.push_back(remaining);
sum+=remaining;
}
if(factors.size()==1){
cout<<"No\n";
return 0;
}
bool first=true;
// Ones adjust the sum while preserving the prime-factor product.
for(int i=0;i<n-sum;i++){
if(!first){
cout<<' ';
}
cout<<1;
first=false;
}
for(int factor:factors){
if(!first){
cout<<' ';
}
cout<<factor;
first=false;
}
cout<<'\n';
}