Statistics

Problem Statement for "Apportionment"

Problem Statement

A square is divided into N * M equal rectangles.
For example, here's a square divided into 2 * 3 rectangles:
+--+--+--+
|**|**|**|
|**|**|**|
|**|**|**|
+--+--+--+
|**|**|**|
|**|**|**|
|**|**|**|
+--+--+--+
 Find the number of squares made up by these rectangles, i.e., all vertices of squares must coincide with one of the rectangles' vertices. You should count only squares with non-zero area. Two squares are equal if and only if they share the exact same set of vertices. Only count squares whose sides are parallel to the sides of the original square.

Definition

Class:
Apportionment
Method:
numberOfSquares
Parameters:
int, int
Returns:
long
Method signature:
long numberOfSquares(int N, int M)
(be sure your method is public)

Constraints

  • N and M will each be between 1 and 100000, inclusive.

Examples

  1. 1

    1

    Returns: 1

    Here there is only square.

  2. 2

    2

    Returns: 5

    Here there are 4 smaller squares (each of the rectangles is a square), along with the one original square.

  3. 99999

    49999

    Returns: 1

  4. 2

    3

    Returns: 1

  5. 3

    2

    Returns: 1

  6. 1

    100000

    Returns: 1

  7. 100000

    1

    Returns: 1

  8. 6

    4

    Returns: 13

  9. 3

    6

    Returns: 22

  10. 6

    3

    Returns: 22

  11. 5

    6

    Returns: 1

  12. 5

    7

    Returns: 1

  13. 5

    8

    Returns: 1

  14. 5

    9

    Returns: 1

  15. 5

    10

    Returns: 95

  16. 5

    11

    Returns: 1

  17. 5

    12

    Returns: 1

  18. 6

    7

    Returns: 1

  19. 6

    8

    Returns: 21

  20. 6

    9

    Returns: 48

  21. 6

    10

    Returns: 25

  22. 6

    11

    Returns: 1

  23. 6

    12

    Returns: 161

  24. 7

    8

    Returns: 1

  25. 7

    9

    Returns: 1

  26. 7

    10

    Returns: 1

  27. 7

    11

    Returns: 1

  28. 7

    12

    Returns: 1

  29. 8

    9

    Returns: 1

  30. 8

    10

    Returns: 31

  31. 8

    11

    Returns: 1

  32. 8

    12

    Returns: 118

  33. 9

    10

    Returns: 1

  34. 9

    11

    Returns: 1

  35. 9

    12

    Returns: 84

  36. 10

    11

    Returns: 1

  37. 10

    12

    Returns: 43

  38. 11

    12

    Returns: 1

  39. 15

    15

    Returns: 1240

  40. 50

    50

    Returns: 42925

  41. 300

    300

    Returns: 9045050

  42. 579

    579

    Returns: 64869230

  43. 981

    981

    Returns: 315173391

  44. 3021

    3021

    Returns: 9194889811

  45. 4568

    4568

    Returns: 31783346884

  46. 12031

    12031

    Returns: 580547916416

  47. 79291

    79291

    Returns: 166172305890946

  48. 100000

    100000

    Returns: 333338333350000

  49. 63402

    68386

    Returns: 1084018189

  50. 19752

    75666

    Returns: 2283586211

  51. 47920

    44228

    Returns: 1854618266

  52. 12405

    62535

    Returns: 3500004040

  53. 24432

    91788

    Returns: 7880761406

  54. 14720

    99820

    Returns: 224592539230

  55. 88920

    91305

    Returns: 117757223475

  56. 45080

    82376

    Returns: 67476656996

  57. 18585

    81774

    Returns: 1882421423799

  58. 70642

    22477

    Returns: 1698852555296

  59. 68708

    34354

    Returns: 27030255822175

  60. 11244

    33732

    Returns: 1421614422930

  61. 86968

    74544

    Returns: 26845788114220

  62. 43421

    86842

    Returns: 54577759822691

  63. 50000

    100000

    Returns: 83334583325000

  64. 20916

    3486

    Returns: 84731181381

  65. 49825

    89685

    Returns: 14841511452835

  66. 5261

    68393

    Returns: 631010395411

  67. 91098

    71577

    Returns: 14140280327796

  68. 5848

    54704

    Returns: 700012860

  69. 6427

    96405

    Returns: 1327399506658

  70. 6253

    62530

    Returns: 814994053211

  71. 41390

    33112

    Returns: 3781305115905

  72. 6285

    37710

    Returns: 496550139435

  73. 5445

    43560

    Returns: 430504135215

  74. 71487

    66924

    Returns: 2423300986041

  75. 40894

    5842

    Returns: 465240338377

  76. 6347

    38082

    Returns: 511390420530

  77. 26964

    79044

    Returns: 58620544710

  78. 58253

    13443

    Returns: 1169452101441

  79. 27966

    86022

    Returns: 282689973969

  80. 3329

    23303

    Returns: 86088689025

  81. 89280

    59520

    Returns: 52713897508320

  82. 72520

    17672

    Returns: 2803757580

  83. 34480

    62064

    Returns: 4918333077736

  84. 38928

    93559

    Returns: 1

  85. 56289

    54921

    Returns: 1717582418

  86. 1353

    3293

    Returns: 1

  87. 41971

    191

    Returns: 1

  88. 52749

    89401

    Returns: 1

  89. 9017

    94945

    Returns: 1

  90. 60289

    42117

    Returns: 1

  91. 8877

    85229

    Returns: 1

  92. 96219

    4039

    Returns: 1

  93. 76711

    54969

    Returns: 1

  94. 3

    3

    Returns: 14

  95. 99999

    11111

    Returns: 4115164581276

  96. 6

    4

    Returns: 13

  97. 100000

    100000

    Returns: 333338333350000

  98. 3

    3

    Returns: 14

  99. 78272

    54968

    Returns: 9412087308

  100. 5

    10

    Returns: 95

  101. 10

    10

    Returns: 385

  102. 2

    4

    Returns: 7

  103. 210

    330

    Returns: 666595

  104. 12

    8

    Returns: 118

  105. 99564

    99874

    Returns: 2486063455

  106. 6

    144

    Returns: 1701

  107. 10000

    10000

    Returns: 333383335000

  108. 16

    36

    Returns: 586

  109. 400

    500

    Returns: 6611650

  110. 99999

    99999

    Returns: 333328333350000

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: