Даны целые неотрицательные числа n и k. Найти разложение биномиального коэффициента C(n, k) на простые множители.
Первая строка содержит количество тестов t (t ≤ 10). Каждая из следующих t строк является отдельным тестом и содержит числа n и k (0 ≤ n ≤ 105
, 0 ≤ k ≤ n).
Вывести t строк, каждая из которых содержит разложение числа C(n,k) на простые множители для соответствующих входных значений.
Разложение натурального числа N на простые множители следует выводить следующим образом. Если N = 1, то необходимо вывести "1" (без кавычек). Иначе пусть N = p1^a1
... pd^ad
, где p1
, ..., pd
- все различные простые делители числа N, упорядоченные по возрастанию, и a1
, ..., ad
- натуральные числа (ai
равно максимальной степени, в которой pi
делит N). Тогда необходимо вывести строку вида p1[^a1]
* ... * pd[^ad]
. Здесь [^ai]
означает, что не следует писать ^ai
, если ai
= 1.
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;
#define MAX 100001
bool flag;
int primes[MAX], deg[MAX], pr[100];
void factor(int n, int flag)
{
for (int i = 0; pr[i] <= (int)sqrt(1.0*n); i++)
while (n % pr[i] == 0) n /= pr[i], deg[pr[i]] += flag;
if (n > 1) deg[n] += flag;
}
//Решето Эратосфена. Строим массив primes, в котором primes[i] = 1, только если число i простое.
void gen_primes()
{
int i, j;
for (i = 0; i < MAX; i++) primes[i] = 1;
primes[0] = primes[1] = 0;
for (i = 2; i <= sqrt(1.0*MAX); i++)
if (primes[i])
for (j = i * i; j < MAX; j += i) primes[j] = 0;
//Заносим в массив pr простые числа от 2 до sqrt(MAX).
for (j = i = 0; i <= sqrt(1.0*MAX); i++) if (primes[i]) pr[j++] = i;
//В конце массива ставим заглушку(число, квадрат которого строго больше MAX).
pr[j] = MAX;
}
//Моделируем вычисление биномиального коэффициента. На самом деле раскладываем
//на множители все множители, стоящие в числителе и знаменателе дроби
void Cnk(int n, int k)
{
int i;
memset(deg, 0, sizeof deg);
for (i = 1; i <= k; i++) factor(n - i + 1, 1), factor(i, -1);
}
int main() {
gen_primes();
int i, n, k, tests;
scanf("%d", &tests);
while (tests--)
{
scanf("%d %d", &n, &k);
if (k > n - k) k = n - k;
if (n == 1 || !k)
{
printf("1\n");
continue;
}
Cnk(n, k);
//Выводим ответ. Если deg[i] ? 0, то простой множитель i входит в разложение Cnk(n,k) со степенью deg[i].
for (flag = i = 0; i < MAX; i++) {
if (deg[i])
{
if (flag) printf(" * ");
printf("%d", i); flag = 1;
if (deg[i] > 1) printf("^%d", deg[i]);
}
}
printf("\n");
}
return 0;
}
Есть решение которого нет на сайте? Пиши admin@devexe.top