1055. Combinations
https://acm.timus.ru/problem.aspx?space=1&num=1055
思路
对于组合数 C(M,N) 不能使用公式计算最终值,然后再根据最终值,分解质因数,统计质因数个数;
因为这种情况会导致数值越界。
改变思路, 组合数公式实际上可以通过三部分计算得到, C(M, N) = M! / (N! * (M-N)!)
可以分别统计 每一个部分的 质因数
然后在M!的质因数的个数中,剔除 N!和(M-N)!质因数的个数
Code
#include <bits/stdc++.h> using namespace std; map<int,int>mp; int main(){ int m,n; cin>>m>>n; for(int i=1;i<=m;i++){ int num=i; for(int j=2;j*j<=i&&num!=1;j++){ while(num%j==0){ num/=j; mp[j]++; } } if(num!=1){ mp[num]++; } } for(int i=1;i<=n;i++){ int num=i; for(int j=2;j*j<=i&&num!=1;j++){ while(num%j==0){ num/=j; mp[j]--; } } if(num!=1){ mp[num]--; } } for(int i=1;i<=m-n;i++){ int num=i; for(int j=2;j*j<=i&&num!=1;j++){ while(num%j==0){ num/=j; mp[j]--; } } if(num!=1){ mp[num]--; } } int ans=0; for(auto t:mp){ if(t.second!=0){ ans++; } } cout<<ans<<endl; }
标签:1055,--,个数,ACM,int,Combinations,质因数 From: https://www.cnblogs.com/lightsong/p/17022412.html