Нахождение НОД Опции

[Unconnected]

Привет всем.

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

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

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

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

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

Сообщение отредактировано: Unconnected - 22.10.2010 15:46