Занятие 1

Некоторые алгоритмы

Нахождение наибольшего общего делителя двух положительных целых чисел (НОД):

int nod(int a, int b)
{ return b?nod(b,a%b):a;
}

Нахождение наименьшего общего кратного двух положительных целых чисел (НОК):

int nok(int a, int b)
{ return a/nod(a,b)*b;
}

Число сочетаний из `n` по `k` `C_n^k\ =\ {n!}/{k!(n-k)!}` можно найти так:

int c(int n, int k)
{
  int i,r=1;
  for(i=k+1; i<=n; ++i)
    r=r*i/(i-k);
  return r;
}

Можно показать, что при выполнении деления делимое всегда кратно делителю: при выполнении деления на `j` делимое получается как произведение последовательных чисел от `i+1` до `i+j`, и хотя бы одно из этих чисел делится без остатка на `j`.