Equally Spaced Bushes
National Olympiad — Regional round (2026 season)
Submission name: bush.cpp
Problem summary
N bushes occupy consecutive equally spaced positions 1 through N. Keep exactly K bushes so that consecutive retained bushes are equally spaced. Count the possible retained sets.
Input
Two integers N and K.
Output
The number of valid ways to keep K bushes.
Constraints
1 ≤ K ≤ N ≤ 1,000,000.
Worked example
An independently prepared example for this explanation.
Input
6 3
Output
6
Solution analysis
- When K = 1, each of the N individual bushes is a valid choice. Handle this separately because there is no gap between retained bushes.
- For K ≥ 2, a valid set has a first position s and positive integer gap d: s, s+d, …, s+(K−1)d. Its last position must be at most N.
- A fixed gap d allows N−(K−1)d starting positions. Feasible gaps run from 1 through q = floor((N−1)/(K−1)).
- Sum these counts using 1+2+…+q = q(q+1)/2. The answer is q·N − (K−1)·q(q+1)/2.
- For N = 6, K = 3, gap 1 gives four sets and gap 2 gives two sets, for six total. For K = 2 the formula becomes N(N−1)/2, as every pair is valid.
Why it works
Each valid retained set has exactly one first position and, for K≥2, exactly one gap. The inequality on its last position gives all and only its feasible starts. Summing over the feasible gaps counts each set once without omission or duplication.
Watch out. Handle K = 1 before dividing by K−1. Use long long for products: for K = 2 the answer can be 499,999,500,000. The bushes are retained at their original positions, not moved into a new arrangement.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
int main() {
int bushCount, keepCount;
cin >> bushCount >> keepCount;
if (keepCount == 1) {
cout << bushCount << '\n';
return 0;
}
long long largestGap = (bushCount - 1) / (keepCount - 1);
// Sum bushCount - (keepCount - 1) * gap over every feasible gap.
long long gapSum = largestGap * (largestGap + 1) / 2;
long long answer = largestGap * bushCount - (keepCount - 1) * gapSum;
cout << answer << '\n';
}