Square Houses in a City
Autumn Tournament (2024)
Submission name: city.cpp
Problem summary
An N by M grid is cut by full horizontal and vertical streets along cell boundaries. Tile every resulting rectangular block completely with equal K by K square houses, without crossing streets. Find all possible positive integer K. Duplicate streets are allowed.
Input
N M H V; then H horizontal street indices h and V vertical street indices v. A horizontal street h lies before row h, so its coordinate is h−1; vertical indices work analogously.
Output
The number of possible K, then all such K in increasing order.
Constraints
1 ≤ N,M ≤ 10^18; 0 ≤ H,V ≤ 200000; 1 ≤ h ≤ N+1; 1 ≤ v ≤ M+1. Every block side formed by the streets and perimeter is at most 10^14.
Worked example
Original statement sample.
Input
4 6 1 1 3 3
Output
2 1 2
Solution analysis
- A rectangular block can be tiled by K by K squares exactly when both its height and width are divisible by K. Thus K must divide every gap between consecutive horizontal cuts and every gap between consecutive vertical cuts.
- There is no need to sort the cuts: a number divides all gaps exactly when it divides the full side length and every cut coordinate. Start g=gcd(N,M), then combine every h−1 and v−1 into g. The answer consists of all positive divisors of g.
- For the sample, g=gcd(4,6,2,2)=2. Its divisors are 1 and 2. Enumerate trial divisors d≤g/d, collecting d and g/d; print the second half in reverse order to obtain increasing output.
Why it works
Divisibility of all coordinates implies divisibility of differences, and divisibility of all successive gaps implies divisibility of all coordinates by summation. Therefore the common valid K are precisely the divisors of g. Each such K tiles every rectangular block by a regular grid of squares.
Watch out. Convert a street index to coordinate by subtracting one. Perimeter and duplicate streets impose no new restriction. Use long long for side lengths and d≤g/d to avoid squaring overflow.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Divisibility of all coordinates implies divisibility of differences, and divisibility of
// all successive gaps implies divisibility of all coordinates by summation. Therefore the common valid
// K are precisely the divisors of g.
#include<iostream>
#include<numeric>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long rows,columns;
int horizontal,vertical;
cin>>rows>>columns>>horizontal>>vertical;
long long common=gcd(rows,columns);
for(int i=0;i<horizontal+vertical;i++){
long long street;
cin>>street;
common=gcd(common,street-1);
}
vector<long long>small;
vector<long long>large;
for(long long divisor=1;divisor<=common/divisor;divisor++){
if(common%divisor==0){
small.push_back(divisor);
if(divisor!=common/divisor){
large.push_back(common/divisor);
}
}
}
cout<<small.size()+large.size()<<'\n';
bool first=true;
for(long long divisor:small){
if(!first){
cout<<' ';
}
cout<<divisor;
first=false;
}
for(auto it=large.rbegin();it!=large.rend();++it){
if(!first){
cout<<' ';
}
cout<<*it;
first=false;
}
cout<<'\n';
}