6.101.Найти наибольший общий делитель двух заданных натуральных чисел, ис-
пользуя алгоритм Евклида.
6.102. Найти наименьшее общее кратное двух заданных натуральных чисел.
6.103. Даны натуральные числа a и b, обозначающие соответственно числитель
и знаменатель дроби. Сократить дробь, т. е. найти такие натуральные числа p и q, не имеющие общих делителей, что
.
p q a b 6.104. Дан прямоугольник с размерами 425 131 . От него отрезают квадраты со сто-
роной 131, пока это возможно. Затем от оставшегося прямоугольника вновь
отрезают квадраты со стороной, равной 425 131 3 32, и т. д. На какие
квадраты и в каком их количестве будет разрезан исходный прямоугольник?
6.105. Дан прямоугольник с размерами
.
a b От него отрезают квадраты макси-
мального размера, пока это возможно. Затем от оставшегося прямоугольника
вновь отрезают квадраты максимально возможного размера и т. д. На какие
квадраты и в каком их количестве будет разрезан исходный прямоугольник?
6.106. Даны целые числа a и b (a > b). Определить:
а) результат целочисленного деления a на b, не используя стандартную опе-
рацию целочисленного деления; б) остаток от деления a на b, не используя стандартную операцию вычисле-
ния остатка.
6.107. Даны натуральные числа m и n. Получить все кратные им числа, не превы-
шающие
.
m n Условный оператор не использовать. Задачу решить двумя
способами.
6.108. В некоторой стране используются денежные купюры достоинством в 1, 2, 4,
8, 16, 32 и 64. Дано натуральное число n. Как наименьшим количеством та-
ких денежных купюр можно выплатить сумму n (указать количество каждой
из используемых для выплаты купюр)? Предполагается, что имеется доста-
точно большое количество купюр всех достоинств.
6.109. Дано натуральное число (пусть запись этого числа в десятичной системе
имеет вид
1
0
...
k k a a a ). Найти:
а) знакочередующуюся сумму цифр этого числа
0
1
...
1
;
k k a a a б) знакочередующуюся сумму цифр этого числа
1
0
...
1
.
k k k a a a
