TopCoder Statistics - Problem Statement

Problem Statement

Consider the function SSR (Squared Sum of square Roots) defined on two positive integer parameters: SSR(A, B) = (sqrt(A)+sqrt(B))^2. We are interested in the cases when the value of the function is also an integer.

Given ints N and M, return the number of ordered pairs (A, B) such that 1 <= A <= N, 1 <= B <= M and SSR(A, B) is an integer.

Definition

Class:: TheSquareRootDilemma
Method:: countPairs
Parameters:: int, int
Returns:: int
Method signature:: int countPairs(int N, int M)
(be sure your method is public)

Notes

The answer to the problem is guaranteed to fit into signed 32-bit integer type under the given constraints.

Constraints

N will be between 1 and 77,777, inclusive.
M will be between 1 and 77,777, inclusive.

Examples

2

2

Returns: 2

Out of the four possible pairs (A, B), only two yield an integer result: SSR(1, 1) = 4 and SSR(2, 2) = 8. On the other hand, SSR(1, 2) = SSR(2, 1) = 3+2*sqrt(2), which is not an integer.
10

1

Returns: 3

SSR(1, 1), SSR(4, 1) and SSR(9, 1) are integers.
3

8

Returns: 5

The valid pairs are (1, 1), (1, 4), (2, 2), (2, 8) and (3, 3).
100

100

Returns: 310
77777

77777

Returns: 543345
77777

72277

Returns: 519638
1

1

Returns: 1
24

1

Returns: 4
25

1

Returns: 5
77777

1

Returns: 278
24

16236

Returns: 1506
8824

56236

Returns: 130313
68824

56232

Returns: 421216
77777

24512

Returns: 278870
25891

5356

Returns: 65001
2929

59599

Returns: 69953
1000

1000

Returns: 4344
10000

10000

Returns: 57296
10000

66869

Returns: 153175
58858

281

Returns: 15860
22

505

Returns: 242
50005

77777

Returns: 418501
50005

7777

Returns: 113985
50005

7

Returns: 1008
1314

1211

Returns: 5594
5925

11

Returns: 521
1113

59999

Returns: 38664
60000

10000

Returns: 144913
70000

66969

Returns: 471387
59414

67002

Returns: 429403
75000

77000

Returns: 528692
75000

49993

Returns: 410419
49945

74935

Returns: 410071
77200

77711

Returns: 540417
77200

51515

Returns: 423769
51295

76123

Returns: 419928
12375

748

Returns: 13542
23895

7895

Returns: 78035
2

77777

Returns: 475
77777

3

Returns: 636
50000

6

Returns: 924
50001

12700

Returns: 152516
77577

77577

Returns: 541493
76765

77777

Returns: 538968
77777

44444

Returns: 390889
77776

77776

Returns: 543344
77771

77771

Returns: 543323
7777

7777

Returns: 43513
77777

70000

Returns: 509807
76513

74797

Returns: 526033
77773

77775

Returns: 543331
33333

77777

Returns: 331955
65536

65536

Returns: 451096
70000

70000

Returns: 484684
77767

77767

Returns: 543313
77763

77764

Returns: 543308
50000

50000

Returns: 336016
77657

77777

Returns: 542785
77555

65666

Returns: 489869
999

666

Returns: 3313
77776

77777

Returns: 543344
77267

75557

Returns: 531659
77777

77775

Returns: 543340
77777

77776

Returns: 543344
101

201

Returns: 440

Statistics

Problem Statement for "TheSquareRootDilemma"

Problem Statement

Definition

Notes

Constraints

Examples