Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 8 ] 
Автор Сообщение
 Заголовок сообщения: (C++)Функция Эйлера от биноминального коэффициента
СообщениеДобавлено: 28 июл 2020, 22:24 
Не в сети
Начинающий
Зарегистрирован:
04 июл 2019, 07:16
Сообщений: 13
Cпасибо сказано: 4
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Здравствуйте, прошу помочь найти неточности, в программе, чтобы понять почему 10 тест в контесте меня не пускает. Задача является третьей задачей яндекс контеста https://contest.yandex.ru/contest/12341/enter/.
______________________________________________________________
#include<iostream>
//#include<cassert>
#define Mod 1000000007

using namespace std;

int Eul(long long n) {
long long res = n;
for (long long i = 2; i <= n/i; ++i)
if (n % i == 0) {
while (n % i == 0) {
n /= i;
}
res-= res / i;
}
if (n > 1) {
res-= res / n;
}
res%=Mod;
res=(int)res;
return res;
}

long long Bin_K(int k, int n) {
long long a=1, b=1;
for (int i = 0;i < k ;i++) {
a *= n - i;
b *= k - i;
}

long long res = a / b;

return res;
}

int
main() {
int n,k;
cin >> k >> n;
cout << Eul(Bin_K(k, n))<<endl;
return 0;
}

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: (C++)Функция Эйлера от биноминального коэффициента
СообщениеДобавлено: 29 июл 2020, 10:04 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 5513
Cпасибо сказано: 84
Спасибо получено:
1193 раз в 1089 сообщениях
Очков репутации: 236

Добавить очки репутацииУменьшить очки репутации
Для просмотра условия требуется авторизация.
Но ошибка у вас скорее всего при расчете биномиального коэффициента. Когда считаете факториалы, то легко можете выйти за пределы long long. 21! уже больше. Надо использовать или big integer или разложение на простые. Первый вариант проще в исполнении, но менее эффективен и может зависнуть на больших числах. Тут зависит, конечно, от порядка чисел.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: (C++)Функция Эйлера от биноминального коэффициента
СообщениеДобавлено: 29 июл 2020, 17:01 
Не в сети
Начинающий
Зарегистрирован:
04 июл 2019, 07:16
Сообщений: 13
Cпасибо сказано: 4
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
Для просмотра условия требуется авторизация.

Вроде можно просто нажать на кнопку участия и всё зайдёт, хотя я если честно давно уже это сделал так что точно не помню, но доступ можно получить вроде точно через эту страницу https://yandexdataschool.ru/enroll#stages выбрав среди примеров заданий пробный контест.

Также спасибо про вариант с изменением типа данных. Вариант с раскладыванием на простые множители элементов при вычислении факториалов думаю вполне сможет решить эту задачу, но для него нужно подумать.
Изображение

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: (C++)Функция Эйлера от биноминального коэффициента
СообщениеДобавлено: 29 июл 2020, 17:17 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 5513
Cпасибо сказано: 84
Спасибо получено:
1193 раз в 1089 сообщениях
Очков репутации: 236

Добавить очки репутацииУменьшить очки репутации
Kosiposha писал(а):
но доступ можно получить вроде точно через эту страницу

Для этого надо иметь регистрацию на яндексе, чего делать совершенно не желаю.
В любом случае не стоит заставлять людей, от которых вы просите помощи, ходить на сторонние сайты, если, потратив 5 минут своего времени, вы в состоянии написать в ТеХе условие полностью.
3 секунды и 500000 не оставляют вариантов - нужно использовать представление числа, как произведение степеней простых. Что, конечно, идейно правильно. В конкурсных заданиях не должны проходить топорные прямолинейные решения

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: (C++)Функция Эйлера от биноминального коэффициента
СообщениеДобавлено: 29 июл 2020, 19:13 
Не в сети
Начинающий
Зарегистрирован:
04 июл 2019, 07:16
Сообщений: 13
Cпасибо сказано: 4
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
swan

Цитата:
Для этого надо иметь регистрацию на яндексе, чего делать совершенно не желаю.

Хорошо, буду выкладывать условие.
Цитата:
нужно использовать представление числа, как произведение степеней простых

Т.е вы предлагаете представлять биноминальный коэффициент как произведение степеней простых? Хорошо, попробуем, подумаем и ещё раз подумаем.
Цитата:
В конкурсных заданиях не должны проходить топорные прямолинейные решения

Вроде не олимпиада и не конкурс, в любом случае будет полезно.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: (C++)Функция Эйлера от биноминального коэффициента
СообщениеДобавлено: 30 июл 2020, 11:02 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 5513
Cпасибо сказано: 84
Спасибо получено:
1193 раз в 1089 сообщениях
Очков репутации: 236

Добавить очки репутацииУменьшить очки репутации
Kosiposha писал(а):
Т.е вы предлагаете представлять биноминальный коэффициент как произведение степеней простых? Хорошо, попробуем, подумаем и ещё раз подумаем.
Не знаю над чем тут думать, но это действие всегда полезно. Не буду мешать

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: (C++)Функция Эйлера от биноминального коэффициента
СообщениеДобавлено: Вчера, 12:13 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 5513
Cпасибо сказано: 84
Спасибо получено:
1193 раз в 1089 сообщениях
Очков репутации: 236

Добавить очки репутацииУменьшить очки репутации
Интересно, удалось получить что-нибудь?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: (C++)Функция Эйлера от биноминального коэффициента
СообщениеДобавлено: Вчера, 22:45 
Не в сети
Начинающий
Зарегистрирован:
04 июл 2019, 07:16
Сообщений: 13
Cпасибо сказано: 4
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
Интересно, удалось получить что-нибудь?

Пока что ничего не сдвинулось, так как не занимался этой задачей. Если будет что-то результативное напишу.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 8 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Функция Эйлера

в форуме Размышления по поводу и без

ammo77

7

155

18 июл 2019, 17:16

Функция Эйлера

в форуме Теория чисел

demigod324

9

569

12 янв 2014, 12:04

Функция Эйлера

в форуме Теория чисел

ammo77

0

53

19 дек 2019, 18:02

Re: Функция Эйлера

в форуме Размышления по поводу и без

vorvalm

32

728

23 июн 2019, 15:19

Функция Эйлера

в форуме Палата №6

ammo77

214

3323

19 май 2019, 13:53

Функция Эйлера

в форуме Теория чисел

nicat

7

549

21 сен 2015, 07:58

Функция Эйлера

в форуме Теория чисел

Vadim LOL

3

686

08 авг 2013, 18:58

Функция Эйлера

в форуме Теория чисел

AndreyStepanenko1234

1

210

23 ноя 2017, 17:54

Функция Эйлера

в форуме Теория чисел

AndreyStepanenko1234

3

320

23 ноя 2017, 16:34

Функция Эйлера и теорема 120

в форуме Теория чисел

afraumar

3

456

02 сен 2013, 15:00


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2020 MathHelpPlanet.com. All rights reserved