Cutting a Rectangle into Largest Squares
National Olympiad — Municipal round (2009 season)
Submission name: square.cpp
Problem summary
Repeatedly remove a largest possible square from the remaining rectangle until no material remains. Count all squares, including the final square.
Input
Two positive integers n and m, the rectangle dimensions.
Output
The number of squares.
Constraints
1 ≤ n,m ≤ 10^18.
Worked example
Input and output for the worked example discussed below.
Input
3 7
Output
5
Solution analysis
- If the shorter side is a and the longer side b, the next square has side a. Instead of subtracting a once, remove all floor(b/a) such squares together. The remaining rectangle has dimensions a and b mod a.
- This is the same remainder transition as Euclid’s gcd algorithm, but accumulate each quotient. Stop when the remainder is zero; that final division has already counted the final square.
- For 3×7, two 3×3 squares leave 3×1. Three 1×1 squares fill the rest, so the total is 2+3=5. Equal dimensions require exactly one square. Quotient grouping also handles a 1×10^18 rectangle immediately.
Why it works
Each of the next floor(b/a) largest squares must have side a and leaves exactly the same remainder as repeated single removals. Thus grouping does not change the cutting sequence or its count. Applying the argument to every smaller remainder rectangle counts all squares.
Watch out. Do not simulate each removed square individually. Count the final square; otherwise equal sides incorrectly give zero. Use 64-bit dimensions and answer.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<cmath>
#include<iostream>
#include<limits>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<vector>
using namespace std;
int main(){
long long a;
long long b;
cin>>a>>b;
long long squares=0;
while(b!=0){
// One division groups all equal-sized square removals.
squares+=a/b;
long long remainder=a%b;
a=b;
b=remainder;
}
cout<<squares<<'\n';
}