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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
petya_prog
4 / 4 / 1
Регистрация: 26.04.2013
Сообщений: 61
#1

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

10.03.2014, 14:07. Просмотров 598. Ответов 6
Метки нет (Все метки)

Торт от Толи
Толя на день рождения собирается угостить друзей тортом. Известно, что на дне рождения может быть либо 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 процентов!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.03.2014, 14:07     Задача на теорию чисел
Посмотрите здесь:

Задача на теорию автоматов - C++
Условие во вложение. Не совсем понимаю алгоритм. Есть какие-нибудь идеи?

Задача на программирование и теорию вероятностей - C++
Требуется написать фрагмент тела функции, который присваивает переменным a, b и c такие случайные целые значения, которые удовлетворяют...

Объясните бинарные файлы (теорию) - C++
С реализацией разобрался, но плохо осведомлён теорией. На примере структуры. У нас есть структура и нам нужно занести элементы бинарный...

Подскажите литературу теорию и практику по написанию исходного кода на С++ - C++
Подскажите литературу теорию и практику по написанию исходного кода на С++. Если есть с подробным разбором текста по строкам, как и что с...

Работа с файлами C++. Где взять теорию для написания курсовой? - C++
Нужно написать курсовую на тему Работа с файлами С++. Тему эту я немного изучил из книги Джесс Либерти с++ за 21 день. Помогите найти...

задача сравнить 5 чисел - C++
Только начал изучение С++ В книге есть задача: сравнить 5 произвольно введенных чисел. Решил так // #include &quot;stdafx.h&quot; ...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
S_el
2092 / 1599 / 306
Регистрация: 15.12.2013
Сообщений: 6,427
10.03.2014, 14:11     Задача на теорию чисел #2
Цитата Сообщение от petya_prog Посмотреть сообщение
набирает только 25 процентов!
Всмысле?
А вообще такая тема на форуме точно уже была.
petya_prog
4 / 4 / 1
Регистрация: 26.04.2013
Сообщений: 61
10.03.2014, 14:22  [ТС]     Задача на теорию чисел #3
задача на е-олимпе набирает 25% http://www.e-olimp.com/problems/1033
темы такой не удалось найти, если можете, скиньте пожалуйста
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
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
Сообщений: 61
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
Сообщений: 61
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     Задача на теорию чисел
Еще ссылки по теме:

Задача на поиск 2х наибольших чисел - C++
Попалась задачка с ныне мне не встречавшейся переменной tmp. Единственное, что я нашла в интернете, так это то, что tmp создают для...

Форматы чисел, циклы | задача - C++
Дано n вещественных чисел. Найти количество тех из них, которые после усечения стали больше 15 , четны и кратны 5.

Задача на зашифрование 4-х значных чисел - C++
Всем привет, штурмую Дейтел, сталкнулся с задачей : &quot; Компания хочет передавать данные по телефону, но она обеспокоена возможностью...

Сумма последовательности чисел. Задача - C++
Доброго времени суток помогите решить очень простенькую задачу. В стандартном потоке ввода задаётся последовательность целых чисел....


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru