UVa 530 - Binomial Showdown

663 ワード

テーマ:組み合わせの数C(n,k)を求めます.
分析:数論.この问题は简単な问题ですか、じòぴé(′▽`)∞、いろいろな方法を试みました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; }