**Description:**

Imagine a white rectangular grid of `n`

rows and `m`

columns divided into two parts by a diagonal line running from the upper left to the lower right corner. Now let’s paint the grid in two colors according to the following rules:

- A cell is painted black if it has at least one point in common with the diagonal;
- Otherwise, a cell is painted white.

Count the number of cells painted black.

**Example**

- For
`n = 3`

and`m = 4`

, the output should be

`countBlackCells(n, m) = 6`

.There are

`6`

cells that have at least one common point with the diagonal and therefore are painted black. - For
`n = 3`

and`m = 3`

, the output should be

`countBlackCells(n, m) = 7`

.`7`

cells have at least one common point with the diagonal and are painted black.

**Input/Output**

**[time limit] 3000ms (cs)**

**[input] integer n**The number of rows.

*Constraints:*

`1 ≤ n ≤ 10`

.^{5}**[input] integer m**The number of columns.

*Constraints:*

`1 ≤ m ≤ 10`

.^{5}**[output] integer**The number of black cells.

**Tests:**

**Solution:**

int countBlackCells(int n, int m) { int answer = 0; for (int x = 1; x <= n; x++) { int L = (int) (m * 1L * (x - 1) / n); if (m * 1L * (x - 1) % n == 0) { L--; } int R = (int) (m * 1L * x / n); L = Math.Max(0, L); R = Math.Min(R, m - 1); answer += R - L + 1; } return answer; }

Advertisements

What is 1L?

LikeLike

Convert to the long type

LikeLike

error: ‘Math’ undeclared (first use in this function)

L = Math.Max(0, L);

?

LikeLike

The Math class need the System package. Please use ‘using System;’

LikeLike

Could you please explain?

LikeLike

Because of 1 ≤ n ≤ 105 and 1 ≤ m ≤ 105. m * (x – 1) maybe exceed int.MaxValue. So I convert to long before divide for n.

LikeLike