Integral Slopes in a Square
National Olympiad — Regional round (2015 season)
Submission name: square.cpp
Problem summary
Among nonhorizontal, nonvertical lattice segments inside [0,A]², find the largest integer length and the number of distinct integer lengths.
Input
One integer A.
Output
Maximum length and distinct-length count, or 0 0.
Constraints
0 < A < 20000.
Worked example
An independently prepared example for this explanation.
Input
4
Output
5 1
Solution analysis
- A segment is represented by positive coordinate differences x,y ≤ A. Its length is an integer exactly when (x,y,z) is a Pythagorean triple.
- Generate every primitive triple with Euclid parameters m>n: x=m²−n², y=2mn, z=m²+n², requiring gcd(m,n)=1 and opposite parity. Mark z,2z,… for every scaling whose larger leg remains at most A. Parameters with m²>2A cannot fit, so the search is small.
- For A=4, the only possible length is 5, from leg differences 3 and 4. Different orientations and translations do not create new lengths, so mark lengths in a Boolean array rather than counting generated triples.
Why it works
Every integer right triangle is a positive multiple of one primitive Euclid triple. The leg bound is both necessary and sufficient for placing the corresponding segment in the square. Thus generation marks every feasible integer length and no infeasible one; scanning marked lengths gives exactly both outputs.
Watch out. Exclude zero legs. Count distinct hypotenuse lengths rather than triples. Reject primitive triples whose larger leg already exceeds A.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
// Algorithm: A segment is represented by positive coordinate differences x,y ≤ A.
using namespace std;
int main(){
int a;
cin>>a;
vector<bool>possible(2*a+1,false);
for(int m=2;m*m<=2*a;++m){
for(int n=1;n<m;++n){
if((m-n)%2==0||gcd(m,n)!=1){
continue;
}
int largestLeg=max(m*m-n*n,2*m*n);
int hypotenuse=m*m+n*n;
for(int scale=1;scale*largestLeg<=a;++scale){
possible[scale*hypotenuse]=true;
}
}
}
int largest=0,count=0;
for(int length=1;length<=2*a;++length){
if(possible[length]){
largest=length;
++count;
}
}
cout<<largest<<' '<<count<<'\n';
}