Cで数学的な組み合わせ計算機を作りたい。たとえば、5つの組み合わせ2は10です。unsigned long long
タイプを使用していても、プログラムでオーバーフローの問題が発生します。入力ソースはnとmです。それぞれの数は(5 <= n、m <= 100)と(m <= n)にバインドされています。さらに、コードを下に添付します。私が知らないより大きな数のタイプまたは解決策はありますか?教えてください。よろしくお願いします。
#include <stdio.h>
static unsigned long long gcd(unsigned long long a, unsigned long long b)
{
if(a<b)
return gcd(b, a);
if(b==0)
return a;
return gcd(b, a%b);
}
int main()
{
unsigned long long n, m1, m2, i, j, temp, denominator[101] = {1,}, numerator[101] = {1,}, total_de = 1, total_nu = 1, gcd_result;
scanf("%llu %llu",&n, &m1);
m2 = n - m1;
if(m2 < m1)
{
temp = m1;
m1 = m2;
m2 = m1;
}// m1 is small
denominator[0] = 1; numerator[0] = 1;
for(i=1; i<=m1; i++)
{
denominator[i] = n--;
numerator[i] = i;
}
for(i = 1; i<=m1; i++)
{
for(j = 1; j<=m1; j++)
{
gcd_result = gcd(denominator[i], numerator[j]);
denominator[i] /= gcd_result;
numerator[j] /= gcd_result;
}
}
for(i = 1; i<=m1; i++)
{
total_de *= denominator[i];
total_nu *= numerator[i];
}
// sometimes overflow happened
printf("%llu\n",total_de/total_nu);
return 0;
}