10673. Игра с округлением вниз и вверх

Теорема. Для двух целых чисел x и k всегда существуют такие целые p и q, что

x = p + q

По заданным x и k необходимо найти хотя бы одну такую пару p и q.

Вход. Первая строка содержит количество тестов t (1 £ t £ 1000). Каждая следующая строка содержит два положительных целых числа x и k (x, k < 10⁸).

Выход. Для каждого теста вывести в отдельной строке два числа: p и q. Если таких пар существует несколько, то вывести одну из них. Значения p и q помещаются в 64-битовый целый тип.

Пример входа

3

5 2

40 2

4 6

Пример выхода

-5 5

0 2

0 4

РЕШЕНИЕ

расширенный алгоритм Евклида

Анализ алгоритма

Если x нацело делится на k, то = = x / k. Выбрав p = 0, q = k, получим: 0 * (x / k) + k * (x / k) = x. Пусть x не делится на k. Если n = , то m = = n + 1. Поскольку НОД(n , m) = НОД(n , n + 1) = 1, то исходя из расширенного алгоритма Евклида, существуют такие целые t и u, что 1 = tn + um. Помножив равенство на x, получим x = xtn + xum, откуда p = xt, q = xu.

Пример

Для первого теста имеет место соотношение: 5 = (-5) * + 5 * = (-5) * 2 + 5 * 3.

Реализация алгоритма

При вычислении используем 64-битовый целый тип long long. Для простоты использования переопределим тип:

typedef long long i64;

Расширенный алгоритм Евклида имеет вид:

void gcdext(i64 a,i64 b, i64 *d, i64 *x, i64 *y)

{

i64 s;

if (b == 0)

{

*d = a; *x = 1; *y = 0;

return;

}

gcdext(b,a % b,d,x,y);

s = *y;

*y = *x - (a / b) * (*y);

*x = s;

}

Читаем количество тестов. Для каждого теста вводим значения x и k.

scanf("%d",&tests);

while(tests--)

{

scanf("%lld %lld",&x,&k);

Если x делится на k, то устанавливаем p = 0, q = k.

if (x % k == 0) { p = 0; q = k;}

else

{

Иначе вычисляем n = и m = , запуская расширенный алгоритм Евклида. Он находит такие t и u, что 1 = tn + um. Далее находим p = xt, q = xu и выводим результат.

n = (int)floor(1.0 * x / k); m = (int)ceil(1.0 * x / k);

gcdext(n,m,&g,&t,&u);

p = t * x; q = u * x;

}

printf("%lld %lld\n",p,q);

}