eolymp
bolt
Try our new interface for solving problems
Məsələlər

Домашнее задание

Домашнее задание

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Каких только странных задач не приходится решать школьникам! При этом некоторые из этих задач, являясь абсолютно бессмысленными, требуют достаточно много времени на решение. Так в одной из школ в качестве домашнего задания была дана следующая задача – представить натуральное число в виде суммы степеней двух натуральных чисел. Казалось бы, ничего сложного. Однако, выписав в тетрадку все варианты, когда хотя бы одно из чисел, возводимых в степень, или хотя бы один из показателей равны 1, умные, но ленивые школьники поняли, что для того, чтобы найти остальные варианты, им придется перебрать очень много случаев и об отдыхе на ближайшее время можно забыть.

Тогда они решили за умеренную плату заказать выполнение домашнего задания. Почему бы Вам не заработать немного денег, написав программу, которая найдет остальные варианты?

Giriş verilənləri

В первой строке одно натуральное число N, 1N2000000000.

Çıxış verilənləri

В первой строке одно натуральное число K – количество различных способов представления числа N в виде a^x+b^y таких, что a, b, x, y – натуральные числа, ни одно из них не равно 1, ab и, если a = b, то xy.

Далее K строк по четыре числа a, x, b, y через пробел, каждая из которых заканчивается переходом на новую строку, – способы представления числа N в заданном виде. Эти четверки чисел упорядочены между собой по возрастанию a, а в случае равенства a – по b, в случае равенства a и b по x.

Nümunə

Giriş verilənləri #1
200
Çıxış verilənləri #1
2
10 2 10 2
14 2 2 2