Задача вродебы простая. Определить десятичный вид дроби

[frankenstein]

Даны числа $n$, $m$, надо определить
ее десятичный вид, в случае если это бесконечная периодическая
дробь, выделить период в круглый скобках:

Пример:

$$\frac{1}{3} = 0.(3)$$

$$\frac{1}{2} = 0.5$$

Задачу надо решить алгоритмически, ну, я получил цифры после
запятой и попытался искать повторяющуюся строку, но для некоторых
чисел период вообще большой получается.

Есть какие нибудь математические методы?

[provincialka]

Период десятичной дроби $m/n$ не может по длине быть больше, чем $n-1$. Эта граница достигается: известный пример - $1/7$.
С другой стороны, период будет делителем числа $99...9$ для подходящего числа девяток.

Нет, там еще могут повлиять двойки и пятерки.

[frankenstein]

Получается так:
Если $m > n$, отбрасываем целую часть.
Находим подходящее кол-во девяток, а оно подходящее
если $n$ нацело делит $999...9$,
затем умножаем полученное число на числитель, остаток
от деленая $m$ на $n$.

Я бы мог найти подходящее количество девяток перебором, но думаю
что это будет довольно медленно.

[provincialka]

Я там отредактировала немного.
Сейчас убегаю, буду часа через два. Может, еще кто подключится. Или ждите меня.

А вы знаете малую теорему Ферма?

[frankenstein]

provincialka в сообщении #941800 писал(а):

А вы знаете малую теорему Ферма?

Нет

[Sonic86]

frankenstein в сообщении #941801 писал(а):

provincialka в сообщении #941800 писал(а):

А вы знаете малую теорему Ферма?

Нет

Ознакомьтесь. И с теоремой Эйлера заодно и с функцией Кармайкла. Жить станет легче.

[frankenstein]

Sonic86 в сообщении #941820 писал(а):

frankenstein в сообщении #941801 писал(а):

provincialka в сообщении #941800 писал(а):

А вы знаете малую теорему Ферма?

Нет

Ознакомьтесь. И с теоремой Эйлера заодно и с функцией Кармайкла. Жить станет легче.

Ок

[Deggial]

Заголовок темы изменён без согласия с ТС.
frankenstein, давайте, пожалуйста, темам содержательные названия.

[frankenstein]

Deggial в сообщении #941828 писал(а):

Заголовок темы изменён без согласия с ТС.
frankenstein, давайте, пожалуйста, темам содержательные названия.

Ладно

[Александрович]

frankenstein в сообщении #941791 писал(а):

Пример:

$$\frac{1}{3} = 0.(3)$$

$$\frac{1}{2} = 0.5$$

Формально $\frac{1}{2} = 0.5(0)=0.4(9)$.

[frankenstein]

круто!

[arseniiv]

frankenstein, если делить как в школе, то начало повтора определяется по повторению очередного остатка — раз он совпал, дальше результаты делений совпадут тоже.

[provincialka]

Вообще многое зависит от того, насколько "продвинутую" программу надо делать. Одно дело - учебная однодневка, лишь бы считала. Другое - оптимизированная солидная программа, которая может справиться с огромными числами.

[frankenstein]

Программа должна уметь работать с таким диапазоном чисел:
$0 \le N,M \le 100000$

Да, думаю школьный метод сработает.

provincialka, я просто пытаюсь решить задачу на http://train.usaco.org

[provincialka]

А почему у меня "Веб-страница недоступна"?