Lattice Points Under a Line
Compute ∑i=0..N−1 ⌊(A·i + B) / C⌋ — the number of lattice points strictly under the line, summed columnwise.
Input: one line with four integers A, B, C, N.
Output: the floor-sum value.
Constraints:
- 0 ≤ A, B < 109
- 1 ≤ C, N ≤ 109
Sample Tests
Input 1
1 0 2 5
Output 1
4
Input 2
3 2 4 3
Output 2
3
Discussion (opens after you solve — no spoilers before)
No comments yet.