1. 数学作业
【问题描述】
路人丙的数学老师非常乏力，他喜欢出一些非常乏力的数学题来为难乏力的学生们。这次数学老师布置了一堆的数学题作为作业，而且这些数学题有个共同的特点是都求C(N,M)中不同质因子的个数，所以路人丙需要你帮他写一个程序来帮助他快速地完成这些作业。C(N,M)即求在N中选M个的组合数。
【输入文件】
输入N,M（1<=N,M<=50000）
【输出文件】
输出一个整数
【样例输入】
7 3
【样例输出】
2
解：数论题；不用求组合数和杨辉三角；
否则会爆内存；正确做法：先做一个质数表； 然后先分母，后分子，每一个分解质因数，分母每有一个质数，利用【数组】++， 分子分解【质数】--； 最后遍历，有则代表组合数的质因数分解； 则ans++； 最后输出即可；1 #include2 #include 3 #define sc(x) scanf("%d",&x) 4 #include 5 #include 6 #include 7 #include 8 #define man 50000+10 9 using namespace std;10 int n,m;11 int tot=0;12 int prime[man];13 bool a[man];14 int ans=0;15 int c[man];16 void mktb(int n)17 {18 for(int i=2;i<=n;i++)19 {20 if(!a[i])21 prime[++tot]=i;22 for(int j=1;j*prime[i]<=n;j++)23 {24 a[prime[i]*j]=1;25 if(i%prime[j]==0)26 break;27 }28 }29 }30 void calc1(int n)31 { for(int i=1;i<=tot&&prime[i]<=n;i++)32 {33 while(n%prime[i]==0)34 {35 c[i]++;36 n=n/prime[i];37 }38 }39 }40 void calc2(int n)41 { for(int i=1;i<=tot&&prime[i]<=n;i++)42 {43 while(n%prime[i]==0)44 {45 c[i]--;46 n=n/prime[i];47 }48 }49 }50 int main()51 { freopen("math.in","r",stdin);52 freopen("math.out","w",stdout);53 memset(c,0,sizeof(c));54 memset(a,0,sizeof(a));55 sc(n);sc(m);56 mktb(n);57 for(int i=n;i>n-m;i--)58 calc1(i);59 for(int i=2;i<=m;i++)60 calc2(i);61 for(int i=1;i<=n;i++)62 if(c[i])63 ans++;64 printf("%d\n",ans);65 return 0;66 }