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

@petya_prog · Регистрация: 26.04.2013

Author24 — интернет-сервис помощи студентам

Торт от Толи
Толя на день рождения собирается угостить друзей тортом. Известно, что на дне рождения может быть либо 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 · 10.03.2014, 14:11

Сообщение от petya_prog

набирает только 25 процентов!

Всмысле?
А вообще такая тема на форуме точно уже была.

@petya_prog · 10.03.2014, 14:22 **[ТС]**

задача на е-олимпе набирает 25% http://www.e-olimp.com/problems/1033
темы такой не удалось найти, если можете, скиньте пожалуйста

@salam · 10.03.2014, 14:37

вроде ответ такой: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{a * b}{gcd(a, b)}$

@petya_prog · 10.03.2014, 14:55 **[ТС]**

Сообщение от salam

вроде ответ такой: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{a * b}{gcd(a, b)}$

это если бы кусочки одинаковые должны были быть

Добавлено через 15 минут

Сообщение от S_el

А вообще такая тема на форуме точно уже была.

если Вы имеете в виду это, то там нет решения

@petya_prog · 23.03.2014, 14:54 **[ТС]**

правильный ответ - a+b-gcd(a,b)

@bulldogg · 18.02.2015, 22:34

ты можешь его математически обосновать?или хоть как то объяснить как взялась эта формула?

Новые блоги и статьи Все статьи Все блоги /
Вопросы на собеседованиях по микросервисам ArchitectMsa 27.03.2025 Работодатели ищут не просто разработчиков, знающих базовые концепции, а специалистов, разбирающихся в тонкостях масштабирования, отказоустойчивости и производительности. Сейчас на первый план выходят. . .	Взаимодействие Python с REST API py-thonny 27.03.2025 REST API - это архитектурный стиль взаимодействия компонентов распределённого приложения в сети. Python располагает функциональным набором инструментов для работы с REST API и основная библиотека для. . .	sshd restrictions, ssh access limitations jigi33 26.03.2025 sshd restrictions \| ssh access limitations рестрикции доступа на сервер sshd статья: https:/ / www. golinuxcloud. com/ restrict-allow-ssh-certain-users-groups-rhel	Компиляция C++ с Clang API NullReferenced 24.03.2025 Компиляторы обычно воспринимаются как черные ящики, которые превращают исходный код в исполняемые файлы. Мы запускаем компилятор командой в терминале, и вуаля — получаем бинарник. Но что если нужно. . .	Многопоточное программирование в C#: Класс Thread UnmanagedCoder 24.03.2025 Когда запускается приложение на компьютере, операционная система создаёт для него процесс - виртуальное адресное пространство. В C# этот процесс изначально получает один поток выполнения — главный. . .
SwiftUI Data Flow: Передача данных между представлениями mobDevWorks 23.03.2025 При первом знакомстве со SwiftUI кажется, что фреймворк предлагает избыточное количество механизмов для передачи данных: @State, @Binding, @StateObject, @ObservedObject, @EnvironmentObject и другие. . . .	Моки в Java: Сравниваем Mockito, EasyMock, JMockit Javaican 23.03.2025 Как протестировать класс, который зависит от других сложных компонентов, таких как базы данных, веб-сервисы или другие классы, с которыми и так непросто работать в тестовом окружении? Для этого и. . .	Архитектурные паттерны микросервисов: ТОП-10 шаблонов ArchitectMsa 22.03.2025 Популярность микросервисной архитектуры объясняется множеством важных преимуществ. К примеру, она позволяет командам разработчиков работать независимо друг от друга, используя различные технологии и. . .	Оптимизация рендеринга в Unity: Сортировка миллиона спрайтов GameUnited 22.03.2025 Помните, когда наличие сотни спрайтов в игре приводило к существенному падению производительности? Время таких ограничений уходит в прошлое. Сегодня геймдев сталкивается с задачами совершенно иного. . .	Образование и практика Igor3D 21.03.2025 Добрый день А вот каково качество/ эффективность ВУЗовского образования? Аналитическая геометрия изучается в первом семестре и считается довольно легким курсом, что вполне справедливо. Ну хорошо,. . .

@S_el 2444 / 1842 / 406 Регистрация: 15.12.2013 Сообщений: 8,243
	10.03.2014, 14:11
	Сообщение от petya_prog набирает только 25 процентов! Всмысле? А вообще такая тема на форуме точно уже была. 0

@petya_prog 4 / 4 / 5 Регистрация: 26.04.2013 Сообщений: 61
	10.03.2014, 14:22 [ТС]
	задача на е-олимпе набирает 25% http://www.e-olimp.com/problems/1033 темы такой не удалось найти, если можете, скиньте пожалуйста 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	10.03.2014, 14:37
	вроде ответ такой: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{a * b}{gcd(a, b)}$ 0

@petya_prog 4 / 4 / 5 Регистрация: 26.04.2013 Сообщений: 61
	10.03.2014, 14:55 [ТС]
	Сообщение от salam вроде ответ такой: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{a * b}{gcd(a, b)}$ это если бы кусочки одинаковые должны были быть Добавлено через 15 минут Сообщение от S_el А вообще такая тема на форуме точно уже была. если Вы имеете в виду это, то там нет решения 0

@petya_prog 4 / 4 / 5 Регистрация: 26.04.2013 Сообщений: 61
	23.03.2014, 14:54 [ТС]
	правильный ответ - a+b-gcd(a,b) 0

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

Опции темы