1306 2249

关键是红色部分，对数的优化

#include <iostream>
using namespace std;

__int64 work(__int64 n,__int64 k)
{

if (k>n-k)
return work(n,n-k);
if ( k == 0 )return 1;
if ( k == 1 )return n;
int i;
__int64 re = work(n-1,k-1);
for ( i = k ; i >= 2 ; i-- )
{
while ( re % i == 0 && k % i == 0 )
{
re /= i;
k/=i;
}
while ( n % i == 0 && k % i == 0 )
{
n /= i;
k/=i;
}
if ( k == 1 ) break;
}
re = re * n ;
return re ;
}

int main ()
{

__int64 n, k;

while ( scanf ( "%I64d%I64d", &n, &k )&&n)
{
printf ( "%I64d things taken %I64d at a time is %I64d exactly.\n", n,k,work( n, k ) );
}
return 0;
}