Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
GORT92
-27 / 0 / 1
Регистрация: 26.01.2013
Сообщений: 23
#1

Найти C(n,k). C(n,k) = (n!/(n-k)!*k!) - C++

24.01.2014, 20:09. Просмотров 484. Ответов 1
Метки нет (Все метки)

2015 год… В Астане проходит IOI 2015! Сильнейшая участник с Казахстана, Нурба решил 5 задач из 6! И он не может решить последнюю задачу. Он очень устал после первых 2-х часов контеста. Так как он у себя на родине, он вышел в туалет и послал SMS Санчо за помощью. Так как у него есть совесть, он попросил решить только подзадачу последней задачи. Подзадача была найти C(n,k). C(n,k) = (n!/(n-k)!*k!). n! = 1*2*3…*n. Так как Санчо очень занятой человек, мы просим вас решить ее. Из-за того что ответ может быть большим, выведите его модулю числа P.
Формат входных данных
Вам даны числа N,K,P. (1 <= K <= N <= 10^6, 1 <= P <= 10^9).
Формат выходных данных
Вывести ответ на задачу.
Пример
Cheating.in
6 2 100
Cheating.out
15
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
gunslinger
случайный прохожий
1146 / 764 / 197
Регистрация: 20.07.2013
Сообщений: 2,137
24.01.2014, 22:52 #2
Не совсем уверен в правильности (правомерно ли вычислять остаток от деления на каждом этапе вычисления?), но вот код на Builder:
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
29
unsigned long long factA (unsigned long n, unsigned long p)
{
  unsigned long long f = 1;
  for (unsigned long i = 1; i <= n; i++)
  {
    f *= i;
    f %= p;
  }
  if (f == 0)
    f = 1;
  return f;
}
//---------------------------------------------------------------------------
unsigned long long factB (unsigned long n, unsigned long k, unsigned long p)
{
  unsigned long long f = 1;
  for (unsigned long i = n-k+1; i <= n; i++)
  {
    f *= i;
    f %= p;
  }
  return f;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button14Click(TObject *Sender)
{
  unsigned long n = 1000, k = 10, p = 1000000000;
  ShowMessage(factB(n, k, p)/factA(k, p));
}
0
Миниатюры
Найти C(n,k). C(n,k) = (n!/(n-k)!*k!)  
Ответ Создать тему
Опции темы

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