Difference of Squares
National Olympiad — Municipal round
Submission name: dif.cpp
Problem summary
Find every pair of nonnegative integers b<a such that x=a²−b². Report the squared values in increasing order of a².
Input
One integer x.
Output
First the number of representations; then a² b² for each. If none exist, print only 0.
Constraints
0 < x < 1,000,000.
Worked example
An independently prepared example for this explanation.
Input
24
Output
2 25 1 49 25
Solution analysis
- Factor x=(a−b)(a+b). Enumerate divisors d≤√x with e=x/d.
- A pair gives integral a=(d+e)/2 and b=(e−d)/2 exactly when d and e have equal parity.
- Store the squared values and sort by the first.
Why it works
Every valid representation yields one positive factor pair d≤e of equal parity, and the inverse formulas produce a unique valid representation from every such pair.
Complexity: O(√x+r log r) time and O(r) memory for r answers.
Watch out. Print a² and b², not a and b. Use 64-bit arithmetic because squares can exceed 32-bit range.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every valid representation yields one positive factor pair d≤e of equal parity, and the
// inverse formulas produce a unique valid representation from every such pair.
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
int main(){
long long x;
cin>>x;
vector<pair<long long,long long>>ans;
for(long long d=1;d*d<=x;d++){
if(x%d==0){
long long e=x/d;
if((d+e)%2){
continue;
}
long long a=(d+e)/2,b=(e-d)/2;
ans.push_back({a*a,b*b});
}
}
sort(ans.begin(),ans.end());
cout<<ans.size()<<'\n';
for(auto[a,b]:ans){
cout<<a<<' '<<b<<'\n';
}
}