Проверка на полный квадрат
Двоичный поиск можно применять к любому упорядоченному набору: списку возрастающих высот, целых чисел, чисел с плавающей точкой и т.д. Аналогичным образом его можно использовать и для множества (целых чисел), множества (натуральных чисел) или множества (рациональных чисел). При этом мы выбираем некоторый диапазон возможных решений и на каждом шаге отбрасываем те части, в которых точно нет ответа.
Задача
Дано положительное целое число
n. Нужно определить, является ли оно квадратным числом (не используя функцию sqrt).Входные данные
На вход подаётся единственное целое число
n (2 ≤ n ≤ ).Выходные данные
Программа должна вывести
Yes, если n — квадратное число, и No в противном случае.Примеры
Входные данные | Выходные данные |
9 | Yes |
8 | No |
16 | Yes |
26 | No |
Подсказка
Если
n — квадратное число, существует некоторое x, для которого . Значит, можно попробовать найти x на отрезке [1, 2, …, n].Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB