Square Counting Challenge

Square Counting Challenge

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 0.5 s

Memory Limit: 256.0 MB

Description

In the bustling land of Algorithma, a new competitive event is underway to test the sharp minds of coders and mathematicians. The challenge? To explore vast grids and uncover the total number of perfect square sub-grids hidden within them. These square sub-grids are highly prized by the kingdom, as they’re known to contain hidden patterns and secrets that only the sharpest minds can reveal.

Given a large grid with dimensions \(H × W\), your task is to count the number of perfect square sub-grids that can be formed within it. A sub-grid is defined by selecting any top-left and bottom-right corners within the grid, and a perfect square sub-grid has equal height and width.

For example, in a \(4×3\) grid:

  • \(A\) \(1×1\) sub-grid is a perfect square.
  • \(A\) \(2×2\) sub-grid is also a perfect square.
  • However, \(A\) \(3×2\) sub-grid is not a perfect square.

Input

The input contains two integers:

  • \(H\) \(( 1≤H≤10^5 )\): the height of the grid.
  • \(W\) \((1≤W≤10^5 )\): the width of the grid.

Output

Print a single integer, the total number of perfect square sub-grids that can be found in the \(H×W\) grid.

Sample

Input Output
5 3
26

Explanation

The \(5×3\) grid has the following perfect square sub-grids:

  • \(1×1\): \(15\) sub-grids
  • \(2×2\): \(8\) sub-grids
  • \(3×3\): \(3\) sub-grids
    The total number of perfect square sub-grids is 15 + 8 + 3 = \(26\).

Brain Booster #7

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
8
Start at
2024-11-05 14:30
End at
2024-11-05 16:45
Duration
2.2 hour(s)
Host
Partic.
142