Форум программистов, компьютерный форум CyberForum.ru

Задача на теорию чисел - C++

Восстановить пароль Регистрация
 
petya_prog
4 / 4 / 1
Регистрация: 26.04.2013
Сообщений: 52
10.03.2014, 14:07     Задача на теорию чисел #1
Торт от Толи
Толя на день рождения собирается угостить друзей тортом. Известно, что на дне рождения может быть либо N, либо M человек, включая самого именинника. На какое минимальное количество частей ему нужно разрезать торт (не обязательно всех равных), чтобы при любом из указанных количестве собравшихся, все съели торт поровну?


Технические условия
Входные данные

В единственной строке два числа через пробел. 1 ≤ M, N ≤ 30000.

Выходные данные

Единственное число – искомое минимальное количество кусочков торта.


вот что написал:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
 
 
using namespace std;
 
typedef long long LL;
 
LL gcd(LL a, LL b)
{
if (b==0) return a;
return gcd(b,a%b);
}
 
int main()
{
LL n,m,d;
cin>>n>>m;
d= gcd(n,m);
d= n*(m/d);
 
if (n>m) swap(m,n);
LL n1,m1;
 
m1= d/m; n1= d/n;
d-= m1*(n-1);
cout<<d<<endl;
return 0;
}
набирает только 25 процентов!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
S_el
1906 / 1501 / 295
Регистрация: 15.12.2013
Сообщений: 5,914
10.03.2014, 14:11     Задача на теорию чисел #2
Цитата Сообщение от petya_prog Посмотреть сообщение
набирает только 25 процентов!
Всмысле?
А вообще такая тема на форуме точно уже была.
petya_prog
4 / 4 / 1
Регистрация: 26.04.2013
Сообщений: 52
10.03.2014, 14:22  [ТС]     Задача на теорию чисел #3
задача на е-олимпе набирает 25% http://www.e-olimp.com/problems/1033
темы такой не удалось найти, если можете, скиньте пожалуйста
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
10.03.2014, 14:37     Задача на теорию чисел #4
вроде ответ такой: http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{a * b}{gcd(a, b)}
petya_prog
4 / 4 / 1
Регистрация: 26.04.2013
Сообщений: 52
10.03.2014, 14:55  [ТС]     Задача на теорию чисел #5
Цитата Сообщение от salam Посмотреть сообщение
вроде ответ такой: http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{a * b}{gcd(a, b)}
это если бы кусочки одинаковые должны были быть

Добавлено через 15 минут
Цитата Сообщение от S_el Посмотреть сообщение
А вообще такая тема на форуме точно уже была.
если Вы имеете в виду это, то там нет решения
petya_prog
4 / 4 / 1
Регистрация: 26.04.2013
Сообщений: 52
23.03.2014, 14:54  [ТС]     Задача на теорию чисел #6
правильный ответ - a+b-gcd(a,b)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.02.2015, 22:34     Задача на теорию чисел
Еще ссылки по теме:

C++ Работа с файлами C++. Где взять теорию для написания курсовой?
C++ Объясните бинарные файлы (теорию)
C++ Задача на программирование и теорию вероятностей

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
bulldogg
1 / 1 / 0
Регистрация: 23.06.2013
Сообщений: 33
18.02.2015, 22:34     Задача на теорию чисел #7
ты можешь его математически обосновать?или хоть как то объяснить как взялась эта формула?
Yandex
Объявления
18.02.2015, 22:34     Задача на теорию чисел
Ответ Создать тему
Опции темы

Текущее время: 13:44. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru