RSS
linjiazhen
分类
标签云
搜索
随机文章
最新评论
最新留言
链接
计数器
146216
UVA 369: Combinations
题目大意:
GIVEN:
Compute the EXACT value of:
给你N和M求C。
解题思路：
由于直接求出阶乘数据庞大，要用高精度算法。但是据题目说答案不超过32位，所以就用新的方法来做。把公式转化为
然后把m+1到n都存入数组，用（n-m）到1去和数组的数一起除以它们的最大公约数。最后把数组里面的数相乘起来就是答案。
解题代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | #include<iostream>using namespace std;typedef long long ll;ll s[105];ll gcd(ll a,ll b){ return a%b==0?b:gcd(b,a%b);}int main(){ ll n,m; while(cin>>n>>m&&m+n){ for(int i=1;i<=n;i++) s[i]=i; ll t=n-m,sum=1; if(t!=0){ while(t!=1){ for(int i=m+1,j=t;i<=n&&j!=1;i++){ ll g=gcd(s[i],j); s[i]/=g; j/=g; } t--; } for(int i=m+1;i<=n;i++) sum*=s[i]; } cout<<n<<" things taken "<<m<<" at a time is "<<sum<<" exactly."<<endl; } return 0;} |