Помощь - Поиск - Пользователи - Календарь
Полная версия: Нахождение НОД
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Unconnected
Привет всем. smile.gif

Занятная задача с окончившейся олимпиады (ну точнее несколько минут осталось, неважно), на нахождение НОД.

Цитата

Заданы два натуральных числа в десятичной системе счисления, состоящие только из единиц. В первом числе ровно N единиц, а во втором их ровно M. Требуется найти наибольший общий делитель этих чисел.
Формат входных данных
В единственной строке входного файла записаны два целых числа N и M (1 ≤ N, M ≤ 100 000).
Формат выходных данных
В выходной файл выведите НОД без ведущих нулей.


Сначала по инерции написал простенький цикл, а потом внимательнее посмотрел на формат входных данных..)) Искать перебором НОД для таких чисел даже длинной арифметикой мне кажется было бы долго, да и не зря же именно единицы в условии..

Я её решил, основываясь на собственной гипотезе (выдвинутой методом научного тыка), что если длина большего числа кратна длине меньшего, то НОД-ом будет меньшее, иначе он будет равен единице. Про первую часть утверждения я почти уверен, а вот про вторую.. как считаете?

added: мда, вторая часть точно ошибочна.. кажется, надо было найти НОД для их длин и в ответ написать количество единиц, равное ему..
мисс_граффити
Цитата
кажется, надо было найти НОД для их длин и в ответ написать количество единиц, равное ему..

очень похоже на правду.
Unconnected
Умная мысля пришла опосля smile.gif Ну хоть не 0 будет..
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.