Counting Sums of Two Positive Squares
National Olympiad — Municipal round (2021 season)
Submission name: squares.cpp
Problem summary
Count input occurrences that equal x²+y² for positive integer roots x,y.
Input
N and N positive values.
Output
The number of representable occurrences.
Constraints
0<N<50000; values≤10000000.
Worked example
Input and output for the worked example discussed below.
Input
4 8 3 5 2
Output
3
Solution analysis
- Read all values and find maximum M. Enumerate positive roots x≤y with x²+y²≤M and mark those sums in a lookup table.
- The symmetry restriction loses no representation because its two roots can be exchanged. Several root pairs may mark the same sum harmlessly.
- For [8,3,5,2], 8=4+4,5=1+4,2=1+1 succeed and 3 fails, giving 3. Count each input occurrence, including duplicates.
Why it works
Every marked value has an explicit positive-square witness. Every valid witness can be ordered x≤y and is visited, proving the lookup exact.
Complexity: O(M+N) time and O(M+N) space; the number of root pairs in a quarter-circle of radius√M is O(M).
Watch out. Zero is not a positive root. Equal roots are allowed.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
// Every marked value has an explicit positive-square witness.
int main(){
int n;
cin>>n;
vector<int>a(n);
int largest=0;
for(int&x:a){
cin>>x;
largest=max(largest,x);
}
vector<unsigned char>possible(largest+1,0);
for(int x=1;2*x*x<=largest;x++){
for(int y=x;x*x+y*y<=largest;y++){
possible[x*x+y*y]=1;
}
}
int answer=0;
for(int x:a){
answer+=possible[x];
}
cout<<answer<<'\n';
}