Рассмотрим массив \(a\), состоящий из всех целых чисел в диапазоне \([l, r]\). Например, если \(l = 3\) и \(r = 7\), то \(a = [3, 4, 5, 6, 7]\).
Учитывая \(l\), \(r\) и \(k\), может ли \(\gcd(a)\) быть больше \(1\) после выполнения следующей операции не более \(k\) раз?
- Выберите \(2\) числа из \(a\).
- Удалите одно вхождение каждого из них из массива.
- Добавьте их произведение в \(a\).
\(\gcd(b)\) обозначает наибольший общий делитель (НОД) всех чисел в \(b\).
Выходные данные
Для каждого тестового примера выведите «YES», если возможно получить НОД соответствующего массива больше, чем \(1\), выполнив не более \(k\) операций, и «NO» в противном случае (без учета регистра).
Примечание
Для первого набора входных данных \(a = [1]\), поэтому ответ «NO», так как единственный элемент в массиве равен \(1\).
Для второго набора входных данных массив равен \(a = [3, 4, 5]\) и у нас есть \(1\) операция. За одну операцию массив может измениться на: \([3, 20]\), \([4, 15]\) или \([5, 12]\), каждый из которых имеет наибольший общий делитель, равный \(1\), поэтому ответ «NO».
Для третьего набора входных данных \(a = [13]\), поэтому ответ «YES», так как единственный элемент в массиве равен \(13\).
Для четвертого набора входных данных \(a = [4]\), поэтому ответ «YES», так как единственный элемент в массиве равен \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
1 1 0
3 5 1
13 13 0
4 4 0
3 7 4
4 10 3
2 4 0
1 7 3
1 5 3
|
NO
NO
YES
YES
YES
YES
NO
NO
YES
|