首页 > 代码库 > 【数论】7041125因子数
【数论】7041125因子数
因子数
7041125因子数 |
| 难度级别：B； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
试题描述 |
计算C(n,k)的因子的个数。 |
输入 |
有多行，每行包含两个正整数 n 和 k ，用一个空格分隔。 |
输出 |
多行，每行包含一个数，依次为各组输入数据对应的结果。 |
输入示例 |
5 1 6 3 10 4 |
输出示例 |
2 6 16 |
其他说明 |
数据范围：0 <= k <= n <= 431。 |
好长时间没有发题解了，今天刷完作业来一发……
显然会炸Long Long，那么即使杨辉三角打表也不行。
有一个公式为：C(N,M)=N!/M!(N-M)!
将其做一个变形，就是C(N,M)=M+1~N连乘/(N-M)!
注意，M+1乘到N与(N-M)！是不一样的。
然后两个循环，将它们的质因子数记录到一个数组里。
最后质因子指数加一再连乘，就得到答案了
代码如下：
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;int ks[1001];int N,M;void fj(int k){ int num=2; while(k!=1){ if(k%num==0) k/=num,ks[num]++; else num++; } return ;}void fj2(int k){ int num=2; while(k!=1){ if(k%num==0) k/=num,ks[num]--; else num++; } return ;}void Num(int N,int M){ for(int i=M+1;i<=N;i++) fj(i); for(int i=1;i<=N-M;i++) fj2(i); return ;}int main(){ while(scanf("%d%d",&N,&M)!=EOF){ memset(ks,0,sizeof(ks)); long long ans=1; Num(N,M); for(int i=1;i<=N;i++) ans*=(ks[i]+1); cout<<ans<<endl; }}
如果有需要，我们也可以将程序用线性筛优化一下：
（然而测评机太慢，给的运行时间与上一个一样……）
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;int ks[501];int map[501];int mark[501];int tot;int N,M;void work(int k,int p){ int num=1; while(k!=1){ if(k%map[num]==0) k/=map[num],ks[map[num]]+=p; else num++; } return ;}void eular(){ mark[1]=1; for(int i=2;i<=500;i++){ if(!mark[i]) map[++tot]=i; for(int j=1;j<=tot;j++){ if(i*map[j]>500) break; mark[i*map[j]]=1; if(i%map[j]==0) break; } } return ;}void Num(int N,int M){ for(int i=M+1;i<=N;i++) work(i,1); for(int i=1;i<=N-M;i++) work(i,-1); return ;}int main(){ eular(); while(scanf("%d%d",&N,&M)!=EOF){ memset(ks,0,sizeof(ks)); long long ans=1; Num(N,M); for(int i=1;i<=N;i++) ans*=(ks[i]+1); cout<<ans<<endl; }}
【数论】7041125因子数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。