TheSquareRootDilemma
SRM 567 · 2012-12-13 · by gojira_tc
SRM 567 · 2012-12-13 · by gojira_tc · Simple Math, Simple Search, Iteration
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.
Givenint s 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.
Given
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
0)
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.
1)
10 1 Returns: 3
SSR(1, 1), SSR(4, 1) and SSR(9, 1) are integers.
2)
3 8 Returns: 5
The valid pairs are (1, 1), (1, 4), (2, 2), (2, 8) and (3, 3).
3)
100 100 Returns: 310
4)
77777 77777 Returns: 543345
Submissions are judged against all 65 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TheSquareRootDilemma with a public method int countPairs(int N, int M) · 65 test cases · 2 s / 256 MB per case