| Математический форум Math Help Planet http://mathhelpplanet.com/ |
|
| Как найти общий делитель 2 чисел? http://mathhelpplanet.com/viewtopic.php?f=10&t=29784 |
Страница 1 из 1 |
| Автор: | medifh [ 01 янв 2014, 18:08 ] |
| Заголовок сообщения: | Как найти общий делитель 2 чисел? |
Числа могут быть очень велики, но состоят из единиц. Например 11111111111111111111 и 111111111111111111111111111111111111111. Нужно найти наибольший общий делитель. Подскажите пожалуйста, хотя бы идею. |
|
| Автор: | dobby [ 01 янв 2014, 18:21 ] |
| Заголовок сообщения: | Re: Как найти общий делитель 2 чисел? |
medifh а чем алгоритм Евклида не устраивает?
|
|
| Автор: | medifh [ 01 янв 2014, 18:59 ] |
| Заголовок сообщения: | Re: Как найти общий делитель 2 чисел? |
dobby писал(а): medifh а чем алгоритм Евклида не устраивает? ![]() Спасибо, не знал про такое. А если числа оооочень большие. Известно что одно из 10^8 единиц состоит, а другое из 10^16 единиц например. Как быть? Может если числа состоят из одной цифры можно через количество разрядов определить? |
|
| Автор: | andrei [ 01 янв 2014, 19:08 ] |
| Заголовок сообщения: | Re: Как найти общий делитель 2 чисел? |
[math]\frac{ 10^{n}-1 }{ 9 }[/math] Так можно представить число,состоящее из [math]n[/math] единиц. |
|
| Автор: | dobby [ 01 янв 2014, 19:11 ] |
| Заголовок сообщения: | Re: Как найти общий делитель 2 чисел? |
Цитата: Может если числа состоят из одной цифры можно через количество разрядов определить? medifh не могу сказать. Есть такое утверждение: пусть [math]r_{n} - n[/math]-значное число [math]11 ... 1.[/math] Тогда: [math](r_{n},r_{m} )=r_{(n,m)}.[/math] Для частных случаев очень эффективно.
|
|
| Автор: | medifh [ 01 янв 2014, 19:48 ] |
| Заголовок сообщения: | Re: Как найти общий делитель 2 чисел? |
Хм, а как мне разделить (10^n-1)/9 на (10^m-1)/9 |
|
| Автор: | Avgust [ 01 янв 2014, 20:01 ] |
| Заголовок сообщения: | Re: Как найти общий делитель 2 чисел? |
Разделить [math]\frac{ 10^{13}-1 }{ 9 }[/math] на [math]\frac{ 10^{18}-1 }{ 9 }[/math] http://www.wolframalpha.com/input/?i=%2 ... %5E18-1%29 Разделить [math]\frac{ 10^{14}-1 }{ 9 }[/math] на [math]\frac{ 10^{18}-1 }{ 9 }[/math] http://www.wolframalpha.com/input/?i=%2 ... %5E18-1%29 |
|
| Автор: | Sonic [ 03 янв 2014, 11:36 ] |
| Заголовок сообщения: | Re: Как найти общий делитель 2 чисел? |
medifh писал(а): Хм, а как мне разделить (10^n-1)/9 на (10^m-1)/9 Вы шутите? Выпишите частное в виде дроби и сокращайте себе наздоровье.
|
|
| Страница 1 из 1 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
| Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |
|