SemiPerfectSquare
SRM 582 · 2012-12-13 · by semiexp
SRM 582 · 2012-12-13 · by semiexp · Brute Force, Simple Search, Iteration
Problem Statement
Problem Statement
Magical Girl Iris loves perfect squares.
A positive integer n is a perfect square if and only if there is a positive integer b >= 1 such that b*b = n.
For example, 1 (=1*1), 16 (=4*4), and 169 (=13*13) are perfect squares, while 2, 54, and 48 are not.
Iris also likes semi-squares. A positive integer n is called a semi-square if and only if there are positive integers a >= 1 and b > 1 such that a < b and a*b*b = n. For example, 81 (=1*9*9) and 48 (=3*4*4) are semi-squares, while 24, 63, and 125 are not. (Note that we require that a < b. Even though 24 can be written as 6*2*2, that does not make it a semi-square.)
You are given aint N.
Return "Yes" (quotes for clarity) if N is a semi-square number.
Otherwise, return "No".
Iris also likes semi-squares. A positive integer n is called a semi-square if and only if there are positive integers a >= 1 and b > 1 such that a < b and a*b*b = n. For example, 81 (=1*9*9) and 48 (=3*4*4) are semi-squares, while 24, 63, and 125 are not. (Note that we require that a < b. Even though 24 can be written as 6*2*2, that does not make it a semi-square.)
You are given a
Notes
- The return value is case-sensitive. Make sure that you return the exact strings "Yes" and "No".
Constraints
- N will be between 2 and 1000, inclusive.
Examples
0)
48 Returns: "Yes"
48 can be expressed as 3 * 4 * 4. Therefore, 48 is a semi-square.
1)
1000 Returns: "No"
1000 can be represented as 10 * 10 * 10, but it doesn't match the definition of semi-perfect squares.
2)
25 Returns: "Yes"
3)
47 Returns: "No"
4)
847 Returns: "Yes"
Submissions are judged against all 101 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SemiPerfectSquare with a public method string check(int N) · 101 test cases · 2 s / 256 MB per case