Fewest Laser Directions on a Grid
National Olympiad — National round (2024 season)
Submission name: shots.cpp
Problem summary
A laser shot from the origin hits every target on its ray. Find the minimum shots hitting all grid points (i,j), 0≤i<M,0≤j<N, except the origin.
Input
M N.
Output
The minimum shot count.
Constraints
3≤M,N≤5000.
Worked example
Input and output for the worked example discussed below.
Input
3 6
Output
10
Solution analysis
- Divide target coordinates by their gcd to obtain a primitive direction. All targets in that direction share one shot aimed at the farthest; distinct directions need separate shots. The two axes contribute two directions.
- Count positive pairs i<M,j<N with gcd(i,j)=1. Factor i into distinct primes. Inclusion-exclusion counts j divisible by none of them; a subset product d divides floor((N−1)/d) possible columns.
- For M=3,N=6, row 1 contributes five directions and row 2 contributes columns 1,3,5. Adding the two axes gives 10. A smallest-prime-factor sieve speeds up each row factorization.
Why it works
Primitive pairs correspond bijectively to rays through targets. Inclusion-exclusion counts exactly the columns sharing no prime factor with the row, which are precisely the primitive positive pairs. One shot per direction is both necessary and sufficient.
Complexity: O(M log log M+Σ 2^ω(i)ω(i)) time and O(M) space. Each i<5000 has at most five distinct prime divisors and 32 subsets.
Watch out. Include axes and use distinct prime factors only. Do not count collinear targets separately.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int rows;
int columns;
cin>>rows>>columns;
vector<int>smallest(rows,0);
for(int prime=2;prime<rows;prime++){
if(smallest[prime]==0){
for(int multiple=prime;multiple<rows;multiple+=prime){
if(smallest[multiple]==0){
smallest[multiple]=prime;
}
}
}
}
int answer=2;
for(int row=1;row<rows;row++){
vector<int>primes;
int value=row;
while(value>1){
int prime=smallest[value];
primes.push_back(prime);
while(value%prime==0){
value/=prime;
}
}
int coprime=columns-1;
for(int mask=1;mask<(1<<primes.size());mask++){
int product=1;
int selected=0;
for(int bit=0;bit<int(primes.size());bit++){
if(mask&(1<<bit)){
product*=primes[bit];
selected++;
}
}
// Inclusion-exclusion corrects overlaps between forbidden multiples.
int multiples=(columns-1)/product;
coprime+=selected%2==0?multiples:-multiples;
}
answer+=coprime;
}
cout<<answer<<'\n';
}