Даны натуральные числа \(a\), \(b\), \(c\). Если уравнение \(ax+by=c\) имеет решения в целых числах, то выберите то решение, в котором число \(x\) имеет наименьшее неотрицательное значение и выведите это решение (два числа \(x\) и \(y\) через один пробел). Если решения не существует, то выведите слово Impossible.

Дано натуральное число \(n \le 10^8\). Подсчитайте количество таких пар чисел \((a, b)\), что:

1. \(a\) и \(b\) — делители \(n\).
2. \(a < b\).
3. \(a\) и \(b\) — взаимно простые.
4. \(ab\le n\).

Завод по производству Крым-колы изготавливает ее не только для магазинов, но и для всемирно известной сети ресторанов быстрого питания.

Ежедневно завод отгружает один и тот же объем колы в литрах. Служба доставки сети ресторанов обычно использует для транспортировки колы емкости объемом или только 50 литров, или только 70 литров. Если доставка осуществляется с помощью емкостей в 50 литров, то для перевозки имеющегося объема колы необходимо A емкостей. А если с помощью емкостей в 70 литров, то необходимо B емкостей. При этом в каждом из случаев одна из емкостей может быть заполнена не полностью.

Недавно сеть ресторанов решила утвердить новый объем емкостей для доставки колы — 60 литров. Сколько емкостей теперь может понадобиться для доставки того же самого объема колы?

Найдите НОД двух чисел.

Сегодня на уроке математики шестиклассник Петя изучил понятие наибольшего общего делителя. Петя тут же решил применить полученные знания на практике.

Петя выписал на листке бумаги \(n\) чисел \(a_1, \ldots, a_n\) --- номера домов, в которых живут его друзья. Теперь он хочет выбрать такое подмножество этих чисел, чтобы их наибольший общий делитель был равен его любимому числу \(d\).

Помогите Пете выбрать из выписанных чисел искомое подмножество.

4 3
6 8 12 9

2
6 9

3 3
2 4 8

-1