质因数计数公式 POJ 2992 Divisors

た入场券 2022-06-04 08:54 123阅读 0赞

Divisors

[http://poj.org/problem?id=2992][http_poj.org_problem_id_2992]

Time Limit:  1000MS

Memory Limit: 65536K

Description

Your task in this problem is to determine the number of divisors of Cnk. Just for fun -- or do you need any special reason for such a useful computation?

Input

The input consists of several instances. Each instance consists of a single line containing two integers n and k (0 ≤ k ≤ n ≤ 431), separated by a single space.

Output

For each instance, output a line containing exactly one integer -- the number of distinct divisors of Cnk. For the input instances, this number does not exceed 2 63 \- 1.

Sample Input

5 1
    6 3
    10 4

Sample Output

2
    6
    16

题目大意：求c(n,m)的因子个数

思路：假设将一个数表示成它的质因数分解，如A=a^p1\*b^p2\*c^p3\*...\*n^pn.

那么它的约数个数就是：ans=(p1+1)\*(p2+1)\*(p3+1)\*...\*(pn+1).

而C(n,k)=n!/\[(k!\*(n-k)!\]，c\[n\]\[k\]代表n的阶乘时能够分解出几个k。

那么只需要求出他们的阶乘对于每一个素数的个数就可以了。

公式：ai=c\[n\]\[prime\[i\]\]-c\[k\]\[prime\[i\]\]-c\[(n-k)\]\[prime\[i\]\]。ans=a1\*a2.\*...\*ak (k代表当prime\[k\]小于n的时候)。

#include <stdio.h>
    using namespace std;
    const int maxn = 432;
    bool vis[maxn];
    int num[maxn][maxn];
    int main()
    {
    	int n,k,i,j,t;
    	//判断素数 
    	for(i=2;i<22;i++)
    	{
    		if(!vis[i])
    		{
    			for(j=i*i;j<maxn;j+=i)
    			vis[j]=true;
    		}		
    	}	
    	//质因数计数公式		
    	for(i=2;i<maxn;i++)
    	{
    		for(j=0;j<=i;j++)
    		num[i][j]=num[i-1][j];
    		t=i;
    		for(j=2;j<maxn&&t>1;j++)
    		{
    			if(!vis[j])
    			{
    				while(t%j==0)
    				{
    					num[i][j]++;
    					t/=j;
    				}
    			}				
    		}			
    	}
    	while(~scanf("%d%d",&n,&k))
    	{
    		__int64 ans=1;
    		if(k&&n-k)//k==0||(n-k)==0时，Cnk为1 
    		{
    			for(i=2;i<=n;i++)
    			{
    				if(!vis[i])
    				ans*=num[n][i]-num[k][i]-num[n-k][i]+1;
    			}				
    		}			
    		printf("%I64d\n",ans);
    	}
    	return 0;
    }

[http_poj.org_problem_id_2992]: http://poj.org/problem?id=2992