IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Нахождение НОД
сообщение
Сообщение #1


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


Привет всем. smile.gif

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

Цитата

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


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

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

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

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


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


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

очень похоже на правду.


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


Умная мысля пришла опосля smile.gif Ну хоть не 0 будет..


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 1.11.2020 4:04
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name