Expert.
Put your skills to the test.

Problem summary

Find the smallest k for which positive integers a1…ak satisfy Π(ai+1)=n·Πai.

Source clarification. The exact-search approach follows the official editorial: https://infos.infosbg.com/files/Contests/ETI/2010/A/analyses/mink_analysis.pdf. This is bounded search, not a claim that ceil(log2 n) always suffices.

Constraints

2<n<1000.

Worked example

An independently prepared worked example; constructive outputs may have other valid forms.

7

4

Solution analysis

1. Rewrite the equation as a product of factors1+1/ai. Every factor is at most2, so start with the smallest k satisfying2^k≥n. This is only a lower bound: n=7 cannot use just three factors.
2. The order of ai is irrelevant, so enumerate nondecreasing denominators. If the still-needed ratio is p/q and there are t factors left, choosing denominator a is possible only when ((a+1)/a)^t≥p/q. This upper bound decreases as a grows and makes every loop finite.
3. After choosing a, replace the ratio by pa/[q(a+1)] and reduce by gcd. With one factor left, solve a=q/(p−q) exactly and test divisibility and the nondecreasing bound. For n=7, four factors can be2·2·(3/2)·(7/6), with denominators1,1,2,6.

Why it works

Sorting the denominators loses no solution. The repeated-largest-remaining-factor bound rejects only choices whose maximum possible completion is too small. The last-factor equation is necessary and sufficient. Exhaustively testing k in increasing order therefore finds the minimum.

Watch out. ceil(log2 n) need not be attainable. Avoid floating-point pruning and huge unreduced products. The implementation reduces each rational transition before multiplication and uses small decimal limbs for exact powers.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<numeric>
#include<vector>
using namespace std;
vector<int>powerProduct(long long factor,int power,long long multiplier){
    const long long base=1000000000;
    vector<int>digits;
    while(multiplier>0){
        digits.push_back(static_cast<int>(multiplier%base));
        multiplier/=base;
    }
    for(int step=0;step<power;step++){
        long long carry=0;
        for(int&digit:digits){
            long long value=digit*factor+carry;
            digit=static_cast<int>(value%base);
            carry=value/base;
        }
        while(carry>0){
            digits.push_back(static_cast<int>(carry%base));
            carry/=base;
        }
    }
    return digits;
}
bool largeEnough(long long p,long long q,int count,long long a){
    auto left=powerProduct(a+1,count,q);
    auto right=powerProduct(a,count,p);
    if(left.size()!=right.size()){
        return left.size()>right.size();
    }
    return !lexicographical_compare(left.rbegin(),left.rend(),right.rbegin(),right.rend());
}
bool possible(long long p,long long q,int count,long long minimum){
    if(p<=q){
        return false;
    }
    if(count==1){
        return q%(p-q)==0&&q/(p-q)>=minimum;
    }
    for(long long a=minimum;largeEnough(p,q,count,a);a++){
        // Cancel cross factors before forming the next reduced fraction.
        long long x=a;
        long long y=a+1;
        long long g=gcd(p,y);
        long long u=p/g;
        y/=g;
        g=gcd(q,x);
        long long v=q/g;
        x/=g;
        if(possible(u*x,v*y,count-1,a)){
            return true;
        }
    }
    return false;
}
int main(){
    int n;
    cin>>n;
    int count=0;
    while((1<<count)<n){
        count++;
    }
    while(!possible(n,1,count,1)){
        count++;
    }
    cout<<count<<'\n';
}