Difference of Cubes
National Olympiad — Municipal round (2011 season)
Submission name: cubes.cpp
Problem summary
For each of two positive input numbers n, find positive integers a>b with a³−b³=n, or report that none exist.
Input
Exactly two positive integers, one per line.
Output
For each input, print any suitable a b, or NO.
Constraints
Each input has at most nine decimal digits.
Worked example
Official statement example.
Input
9 218
Output
NO 7 5
Solution analysis
- Write a=b+d with d>0. Then n=d(3b²+3bd+d²). Since b≥1, d³<n, so it suffices to enumerate d while d³<n. Only divisors d of n can work.
- For each such d, solve the strictly increasing expression 3b²+3bd+d²=n/d by integer binary search. A universal bound b≤20000 is enough because n≥3b²+3b+1 for d≥1, and n<10^9.
- For 218, d=2 leads to 3b²+6b+4=109, satisfied by b=5, hence a=7. For 9 no tested difference gives a positive integer b, so print NO.
Why it works
Every representation has d=a−b with d³<n and d dividing n, and is therefore examined. For fixed d the searched expression is strictly increasing for positive b, so binary search finds b exactly when it exists. Any reported pair is checked by equality; exhausting all d proves impossibility.
Watch out. Natural cube bases are positive: b=0 is not allowed.,Use 64-bit arithmetic for intermediate products.,There are two test numbers, not a leading test count.
Commented C++17 solution
Any valid pair is accepted; a number can have multiple representations.
// Key idea: Every representation has d=a−b with d³<n and d dividing n, and is therefore examined. For
// fixed d the searched expression is strictly increasing for positive b, so binary search finds b
// exactly when it exists.
#include<iostream>
using namespace std;
void solve(long long n){
for(long long d=1;d*d*d<n;++d){
if(n%d!=0){
continue;
}
long long target=n/d;
long long low=1,high=20000;
while(low<=high){
long long b=(low+high)/2;
long long value=3*b*b+3*b*d+d*d;
if(value==target){
cout<<b+d<<' '<<b<<'\n';
return;
}
if(value<target){
low=b+1;
}
else{
high=b-1;
}
}
}
cout<<"NO\n";
}
int main(){
long long first,second;
cin>>first>>second;
solve(first);
solve(second);
}