Combinatorial Expression

In combinatorics the term mainly used is nCr which literally means the number of ways r things can be taken from n things. Mathematically nCr is defined as :

A combinatorial expression may involve many such terms with arithmatic operators. In this problem you have to evaluate a combinatorial expression involving only multiplication and division of nCr.

The Problem

Here a combinatorial expression has two parts. One is numerator and the other is denominator. Both consist of as a mutiplication of several nCr's or a single nCr. A simple expression could be : nCr*nCr / nCr. You have to determine whether the expression produces an integer result ( The numerator is divisible by the denominator). If so then you have to show the result only when the number of digits in the result is less than 101 otherwise just print -1 . If not divisible then print zero only.

The Input

The input will start with two positive integer, N and M (N,M<=100). Each of the following N+M lines will contain two integers (n and r). The first 2*N integers will make the numerator and the next 2*M integers will make the denominator. It is guranteed that no invalid nCr will be present (0<=r<=n<=5000). Input will be terminated by EOF.

The Output

For each test case show the result in a line as specified in the problem statement.

Sample Input

3 3
10 5 
10 4 
10 3
10 7
10 6
10 5
3 3
10 5
10 4
10 3
10 7
10 6
10 1
3 3
10 5
10 4
10 3
10 7
10 6
10 10
4 1
10 5
10 5
10 5
10 5
100 100

Sample Output

1
0
252 
4032758016

Md. Kamruzzaman題目描述：

求 組合連乘積 / 組合連乘積 = ?

如果不能整除輸出 -1，大於 100 位輸出 0。

題目解法：

對於每一個組合 C(n, m) 採用 O(n) 的方式去計算。
預處理每一個數字的質因數分解，因此可以將利用指數的加減法得到

2^r1 * 3^r2 * 5^r3 * 7^r4 * 11^r5 * ...

如果 ri < 0 無法整除。

利用 log 運算，事先得到是否會超過 100 位。

若沒有超過 100 位，使用大數乘法計算答案。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
int f[5500], p[5500], pt = 0;
double LOG[5500];
void sieve() {
    int i, j;
    char mark[5005] = {};
    for(i = 2; i <= 5000; i++) {
        if(mark[i] == 0) {
            for(j = i+i; j <= 5000; j += i)
                mark[j] = 1, f[j] = i;
            f[i] = i;
            p[pt] = i;
            LOG[pt] = log10(i);
            pt++;
        }
    }
}
void addf(int n, int pf[], int val) {
    while(n > 1) {
        pf[f[n]] += val;
        n /= f[n];
    }
}
int main() {
    sieve();
    int n, m;
    while(scanf("%d %d", &n, &m) == 2) {
        int pf[5005] = {};
        int i, j, k, a, b, c;
        for(i = 0; i < n; i++) {
            scanf("%d %d", &a, &b);
            c = a-b;
            if(c < b)    swap(b, c);
            for(j = c+1; j <= a; j++)
                addf(j, pf, 1);
            for(j = 2; j <= b; j++)
                addf(j, pf, -1);
        }        
        for(i = 0; i < m; i++) {
            scanf("%d %d", &a, &b);
            c = a-b;
            if(c < b)    swap(b, c);
            for(j = c+1; j <= a; j++)
                addf(j, pf, -1);
            for(j = 2; j <= b; j++)
                addf(j, pf, 1);
        }
        double product = 0;
        int dividable = 1;
        for(i = 0; i < pt; i++) {
            if(pf[p[i]] < 0) {
                dividable = 0;
                break;
            }
            product += pf[p[i]]*LOG[i];
        }
        if(dividable == 0)
            puts("0");
        else if(product >= 100)
            puts("-1");
        else {
            int ret[35] = {};
            ret[0] = 1;
            for(i = 0; i < pt; i++) {
                if(pf[p[i]] == 0)
                    continue;
                int factor = p[i];
                for(j = pf[p[i]]-1; j >= 0; j--) {
                    for(k = 0; k < 30; k++)
                        ret[k] *= factor;
                    for(k = 0; k < 30; k++) {
                        ret[k+1] += ret[k]/10000;
                        ret[k] %= 10000;
                    }
                }
            }
            k = 30;
            while(ret[k] == 0)    k--;
            printf("%d", ret[k]);
            for(k--; k >= 0; k--)
                printf("%04d", ret[k]);
            puts("");
        }
    }
    return 0;
}