UVa 530 - Binomial Showdown
663 ワード
テーマ:組み合わせの数C(n,k)を求めます.
分析:数論.この问题は简単な问题ですか、じòぴé(′▽`)∞、いろいろな方法を试みましたTLEではなくREで、结果は最も原始的な方法で、GCDでちょっと除いて过ぎました.
注意:データ型、intとlongはTLEになって、すべてlongに変えてACになりました.
分析:数論.この问题は简単な问题ですか、じòぴé(′▽`)∞、いろいろな方法を试みましたTLEではなくREで、结果は最も原始的な方法で、GCDでちょっと除いて过ぎました.
注意:データ型、intとlongはTLEになって、すべてlongに変えてACになりました.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long gcd( long a, long b )
{
return !b?a:gcd( b, a%b );
}
long c( long n, long k )
{
long A = 1L,C;
for ( long i = 1L ; i <= k ; ++ i, -- n ) {
C = gcd( i, n );
A *= n/C;
A /= i/C;
}
return A;
}
int main()
{
long n,k;
while ( scanf("%ld%ld",&n,&k) && n ) {
if ( 2L*k > n ) k = n-k;
printf("%ld
",c( n, k ));
}
return 0;
}