3
|
Задача 245. Деление "единичных" чиселпостоянный адрес задачи: http://www.diofant.ru/problem/610/показать код для вставки на свой сайт >> |
Задачу решили:
6
всего попыток:
8
поделиться задачей:
|
|
|
Задача опубликована:
18.01.10 08:00
Прислал:
morph
(Дмитрий Дремов)
Источник:
Проект "Эйлер" (http://projecteuler.net)
Вес:
1
сложность:
1
класс:
8-10
баллы: 100
Темы:
арифметика
|
|
Лучшее решение:
Anton_Lunyov
|
Рассмотрим "единичные" числа, числа состоящие из нескольких цифр "1". Обозначим R(k) число состоящее из k единиц; например, R(6) = 111111.
Пусть n - натуральное и НОД(n, 10) = 1. Тогда можно показать, что всегда найдется k, такое что R(k) делится на n, обозначим A(n) минимальное из подходящих k. Например, A(7) = 6, А(41) = 5.
Нас интересует отношение n/A(n). Для n<90, n для которого отношение n/A(n) минимально равно 61.
Найдите n для которого n/A(n) минимально среди n<1234567.
Если Вы не можете ее решить, значит Вы не можете ее решить :-)
Обсуждение
Правила >>
Присоединяюсь к выопросу (с той разницей, что Вам уже известен ответ на него). Получается странно:
A(61) = 60
A(3) = 3
3 < 90
НОД(3, 10) = 1
3/3 < 61/60
Я извиняюсь, но всё же A(7)=6, т.е. (2^6-1) mod 7 = 0, но как получается A(41)=5, ведь 2^5-1=31, а 31 не делится на 41?!!!
Здесь числа 111... - в десятичной системе счисления :)