Distinct Sums of Two Squares
National Olympiad — Regional round (2012 season)
Submission name: squares.cpp
Problem summary
Count positive real numbers x such that x²≤S and x² is a sum of two nonnegative integer squares. Different representations of the same squared value count only once.
Input
One integer S.
Output
The number of distinct qualifying x.
Constraints
0<S<20000000.
Worked example
An independently prepared example for this explanation.
Input
25
Output
13
Solution analysis
- The positive square-root function is one-to-one. Thus count distinct positive integers t≤S representable as a²+b², rather than computing any square roots.
- Enumerate nonnegative a and b with a≤b and a²+b²≤S. Mark each resulting value in a Boolean array. Count marked entries from 1 through S.
- For S=5, the possible squared values are 1,2,4,5, giving four distinct positive roots. For S=25, there are thirteen. Values such as 25=0²+5²=3²+4² still count once.
Why it works
Every qualifying squared value has an integer pair that can be ordered with a≤b and is enumerated. Every marked positive value has such a representation. Boolean marking removes precisely duplicate representations, and square roots preserve distinctness.
Watch out. Include zero as a summand, but exclude squared value zero because x must be positive. Counting pairs would overcount repeated sums.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
// Algorithm: The positive square-root function is one-to-one.
using namespace std;
int main(){
int limit;
cin>>limit;
vector<bool>possible(limit+1,false);
for(int a=0;2*a*a<=limit;a++){
for(int b=a;a*a+b*b<=limit;b++){
possible[a*a+b*b]=true;
}
}
int answer=0;
for(int value=1;value<=limit;value++){
answer+=possible[value];
}
cout<<answer<<'\n';
}