Программирование различных типов задач (стр. 3 из 3)
Если a =
, b = 
, где ai, bi >= 0, то, очевидно, что НОД(a, b) = 
и НОК(a, b) = 
. Отсюда, учитывая, что max{x,y}+min{x,y} = x+y, получаем ab = НОД(a, b)НОК(a, b).Найдем НОД(a, b). Верны следующие равенства:
1) НОД(a, b) = НОД(b, a) – следует из определения.
2) НОД(a, 0) = a – очевидно.
3) НОД(a, b) = НОД(a mod b, b).
Доказательство. Докажем сначала, что НОД(a, b) = НОД(a-b, b). Пусть c – общий делитель a и b. Тогда a = kc, b = lc, a-b = (k-l)c, поэтому с – общий делитель a-b и b. Аналогично показывается, что если c – общий делитель (a-b) и b, то с – общий делитель a и b. Поэтому множества общих делителей пар (a, b) и (a-b, b) совпадают. А значит НОД(a,b) = НОД(a-b, b). Применяя эту формулу a div b раз, получим требуемое.
Для нахождения НОД можно использовать следующий алгоритм Евклида:
While (a<>0) and (b<>0) do
If a>b then a:= a mod b
else b:= b mod a;
nod:= a+b;
Корректность этого алгоритма следует из вышеуказанных свойств НОДа.
Справедливо следующее утверждение: существует целые числа u и v такие, что au+bv = НОД(a, b).
Доказательство. Находя НОД по алгоритму Евклида, мы, по сути дела, записали следующие равенства: a = q1b+r1, b = q2r1+r2, …, rn = qn+2rn+1+rn+2, rn+1 = qn+3rn+2. Причем НОД(a, b) = rn+2. Развернем эту цепочку равенств в другую сторону: НОД(a, b) = rn+2 = rn-qn+2rn+1 = rn-qn+2(rn-1-qn+1rn) = -qn+2rn-1+(1+qn+2qn+1)rn = krn-1+lrn = … = Ab+Br1 = Ab + B(a-q1b) = Ba + (A-Bq1)b = au + bv, что и требовалось доказать.
Из этого доказательства следует алгоритм нахождения u и v по a и b.
И в заключении рассмотрим задачу, предлагавшуюся на одной из олимпиад прошлых лет.
Красивые числа
| Имя входного файла: | numbers.in |
| Имя выходного файла: | numbers.out |
| Максимальное время работы на одном тесте: | 1 секунда |
| Максимальный объем используемой памяти: | 64 мегабайта |
Саша считает красивыми числа, десятичная запись которых не содержит других цифр, кроме 0 и k (1 ≤ k ≤ 9). Например, если k = 2, то такими числами будут 2, 20, 22, 2002 и т.п. Остальные числа Саше не нравятся, поэтому он представляет их в виде суммы красивых чисел. Например, если k = 3, то число 69 можно представить так: 69 = 33 + 30 + 3 + 3.
Однако, не любое натуральное число можно разложить в сумму красивых целых чисел. Например, при k = 5 число 6 нельзя представить в таком виде. Но если использовать красивые десятичные дроби, то это можно сделать: 6 = 5.5 + 0.5.
Недавно Саша изучил периодические десятичные дроби и начал использовать и их в качестве слагаемых. Например, если k = 3, то число 43 можно разложить так: 43 = 33.(3) + 3.(3) + 3 + 3.(3).
Оказывается, любое натуральное число можно представить в виде суммы положительных красивых чисел. Но такое разложение не единственно — например, число 69 можно также представить и как 69 = 33 + 33 + 3. Сашу заинтересовало, какое минимальное количество слагаемых требуется для представления числа n в виде суммы красивых чисел.
Требуется написать программу, которая для заданных чисел n и k находит разложение числа n в сумму положительных красивых чисел с минимальным количеством слагаемых.
Формат входных данных
Во входном файле записаны два натуральных числа n и k (1 ≤ n ≤ 109; 1≤ k ≤ 9).
Формат выходных данных
В выходной файл выведите разложение числа n в сумму положительных чисел, содержащих только цифры 0 и k, количество слагаемых в котором минимально. Разложение должно быть представлено в виде:
n=a1+a2+...+am
Слагаемые a1, a2, ..., am должны быть выведены без ведущих нулей, без лишних нулей в конце дробной части. Запись каждого слагаемого должна быть такой, что длины периода и предпериода дробной части имеют минимально возможную длину. Например, неправильно выведены числа: 07.7; 2.20; 55.5(5); 0.(66); 7.(0); 7. ; .5; 0.33(03). Их следует выводить так: 7.7; 2.2; 55.(5); 0.(6); 7; 7; 0.5; 0.3(30).
Предпериод и период каждого из выведенных чисел должны состоять не более чем из 100 цифр. Гарантируется, что хотя бы одно такое решение существует. Если искомых решений несколько, выведите любое. Порядок слагаемых может быть произвольным.
Выходной файл не должен содержать пробелов.
Примеры
| numbers.in | numbers.out |
| 69 3 | 69=33+33+3 |
| 6 5 | 6=5.5+0.5 |
| 10 9 | 10=9.(9) |
Разбор задачи «Красивые числа»
Рассмотрим искомое равенство:
n = a1 + a2 + ... + am,
где каждый ai состоит только из цифр 0 и k.
Разделим обе части на k. Понятно, что при этом в числах ai все цифры k заменятся на единицы, а нули останутся нулями.
Получается новая формулировка задачи: представить число n / k как сумму чисел, состоящих только из цифр 0 и 1. Утверждается, что ответ на нее таков: минимальное количество слагаемых равно максимальной цифре в десятичной записи числа n / k.
Докажем сначала, что меньшим числом слагаемых обойтись нельзя. Будем действовать от противного: предположим, что можно обойтись меньшим числом слагаемых. При этом, так как максимальная цифра в n / k не превышает 9, то мы предполагаем, что можно обойтись не более чем восемью слагаемыми. Выпишем эти слагаемые друг под другом (даже если они бесконечные) и сложим «в столбик». При этом переносов не будет (все цифры 0 или 1, и цифр в каждом столбце не больше 8). Рассмотрим тот столбец, в котором при суммировании должна получиться максимальная цифра из десятичной записи n / k. Даже если во всех слагаемых в этом столбце стоят единицы, все равно нужная сумма не набирается. Получили противоречие; утверждение доказано.
Теперь, пожалуй, понятно, как добиться описанного выше ответа: надо просто в каждом столбце расставить столько единиц, сколько нужно получить в сумме – это соответствующая цифра из n / k.
Пример. Пусть n = 15, k = 7.
15/7 = 2,(142857)
Максимальная цифра — 8. Подберем соответствующие восемь слагаемых.
1,(111111)
1,(011111)
0,(010111)
0,(010111)
0,(000111) +
0,(000101)
0,(000101)
0,(000100)
----------
2,(142857)
Теперь умножим эти числа на 7, и получим следующее верное равенство:
15 = 7,(7) + 7,(077777) + 0,(070777) + 0,(070777) + 0,(000777) + 0,(000707) + 0,(000707) + 0,(000700)
Таким образом, правильное решение состоит из следующих этапов: представление числа n / k в удобном для обработки формате (с аккуратным учетом периода), составление искомых слагаемых и их вывод с учетом имеющихся требований.
Список используемой литературы:
1. Стивен С. Скиена, Мигель А. Ревилла Олимпиадные задачи по программированию, Москва Кудиц-Образ, 2005
2. Немнюгин С.А. TurboPascal, издательский дом «Питер», 2004