All perfect-power representations
National Olympiad — Municipal round
Submission name: stepen.cpp
Problem summary
Find every representation X=a^b with positive integer base a and integer exponent b>1.
Input
X.
Output
First the number of representations; then base and exponent pairs, sorted by decreasing base.
Constraints
2 ≤ X ≤ 10^9.
Worked example
An independently prepared example for this explanation.
Input
64
Output
3 8 2 4 3 2 6
Solution analysis
- Try exponents 2 through 29: larger exponents with base≥2 exceed the bound.
- For each exponent binary-search its integral root. Compare powers using bounded multiplication instead of floating-point rounding.
- Keep exact roots and sort by decreasing base.
Why it works
Every valid exponent lies in the checked range and powers strictly increase with positive base. Exact root search finds precisely all representations.
Complexity: O(log² X · log X) elementary multiplications (at most 29·30·29 here); O(log X) space.
Watch out. Avoid floating-point root equality and overflow when testing powers.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every valid exponent lies in the checked range and powers strictly increase with positive
// base. Exact root search finds precisely all representations.
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
int main(){
long long x;
cin>>x;
vector<pair<long long,int>>ans;
for(int b=2;b<=29;b++){
long long lo=2,hi=x;
while(lo<=hi){
long long a=(lo+hi)/2,p=1;
for(int j=0;j<b;j++){
if(p>x/a){
p=x+1;
break;
}
p*=a;
}
if(p==x){
ans.push_back({a,b});
break;
}
if(p<x){
lo=a+1;
}
else{
hi=a-1;
}
}
}
sort(ans.rbegin(),ans.rend());
cout<<ans.size()<<'\n';
for(auto[a,b]:ans){
cout<<a<<' '<<b<<'\n';
}
}