Задача №114658. Мегакалькулятор <<Заочник~--- 2020>>
Третьего дня, по совету проверенных коллег, вы приобрели новый мегакалькулятор «Заочник — 2020». Сразу же, задыхаясь от нетерпения, вы вскрыли упаковку и опробовали мегакалькулятор.
У «Заочник — 2020» есть всего две кнопки: «\(+\)» и «\(*\)». В течение следующих \(t\) дней вы тестировали мегакалькулятор.
В \(i\)-й день вы запрограммировали мегакалькулятор так, чтобы нажатие на кнопку «\(+\)» прибавляло к числу значение \(p_i\), а нажатие на кнопку «\(*\)» умножало число на \(q_i\).
Затем вы пытались получить из числа \(0\) число \(n_i\), используя ровно \(a_i\) нажатий на кнопку «\(+\)» и ровно \(b_i\) нажатий на кнопку «\(*\)».
Для каждого дня вы хотите узнать, возможно ли получить из числа \(0\) число \(n_i\) при помощи указанных операций.
В первой строке задано одно целое число \(t\) (\(1 \le t \le 10^5\)).
В следующих \(t\) строках заданы пять целых чисел \(p_i\), \(q_i\), \(a_i\), \(b_i\) и \(n_i\) (\(1 \leq p_i \leq 10^9\), \(2 \leq q_i \leq 10^9\), \(0 \leq a_i, b_i \leq 10^9\), \(0 \leq n_i \leq 10^{18}\)).
Выведите \(t\) строк. Если в \(i\)-й день (\(1 \le i \le t\)) можно получить из числа \(0\) число \(n_i\), выведите «Yes», иначе выведите «No».
Рассмотрим пример. Число \(18\) можно получить, нажимая последовательность \(+****++\) (\(0 \rightarrow 1 \rightarrow 2 \rightarrow 4 \rightarrow 8 \rightarrow 16 \rightarrow 17 \rightarrow 18\)) или \(*++**+*\) (\(0 \rightarrow 0 \rightarrow 1 \rightarrow 2 \rightarrow 4 \rightarrow 8 \rightarrow 9 \rightarrow 18\)).
Тесты к этой задаче состоят из семи групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Дополнительные ограничения | |||||||||
| Группа | Баллы | t | p | q | n | a | b | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | – | – | – | Тесты из условия. |
| 1 | 10 | \(t \le 20\) | – | – | – | \(a \le 11\) | \(b \le 11\) | 0 | |
| 2 | 18 | \(t \le 3\) | – | – | \(n \le 30000\) | \(a \le 60\) | \(b \le 60\) | 0 | |
| 3 | 10 | \(t \le 3\) | – | – | \(n \le 30000\) | \(a \le 60\) | – | 0, 2 | |
| 4 | 12 | – | – | – | – | – | \(b \le 1\) | – | |
| 5 | 20 | – | \(p = 1\) | \(q = 2\) | – | – | – | – | |
| 6 | 20 | – | \(p = 1\) | – | – | – | – | 5 | |
| 7 | 10 | – | – | – | – | – | – | 0–6 | |
3 1 2 3 4 18 5 7 2 1 70 5 7 2 1 71
Yes Yes No