Testing Two-Square Representations
National Olympiad — Municipal round (2023 season)
Submission name: squares.cpp
Problem summary
For each value test whether it is the sum of two positive perfect squares.
Input
n and n positive queries.
Output
One binary string with one bit per query.
Constraints
0<n<50000; values<500000.
Worked example
Input and output for the worked example discussed below.
Input
4 16 25 7 50
Output
0101
Solution analysis
- Precompute x²+y² up to the maximum query using positive roots x≤y. Mark every visited sum.
- Read lookup flags in query order and print them without spaces. This version requires per-value bits, not a total count as in the earlier square-sum task.
- Here16 fails,25=3²+4² succeeds,7 fails, and50=1²+7² succeeds. Therefore the result is0101.
Why it works
Marked values have explicit positive-square witnesses. Any witness can be ordered x≤y and is enumerated, so every lookup is exact.
Complexity: O(M+n) time and O(M+n) space for maximum query M; O(M) root pairs are visited.
Watch out. Zero roots are forbidden, equal positive roots allowed. Preserve query order and omit spaces between bits.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
// Marked values have explicit positive-square witnesses.
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;
}
}
for(int x:a){
cout<<(possible[x]?'1':'0');
}
cout<<'\n';
}