Биномиальные коэффициенты 2

Даны целые неотрицательные числа 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;
}