poj 2992 Divisors

poj 2992 Divisors

題目大意：就是叫你求組合數C（n,m）的因子的個數。

思路：求解這題需要用到以下幾個定理

1、對任意的n，可以這麼表示 n=p1^e1*p2^e2*p3*e3*......pn^en 。(p1,p2,p3......pn都為素數)

2、對任意的n的因子數為:(1+e1)*(1+e2)*(1+e3)*......*(1+en)

3、n!的素數因子=（n-1）!的素數因子+n的素數因子

4、C(n,k)的素因子=n!的素因子 - （n-k）!的素因子 - k！的素因子

有了上面介紹的幾個定理那麼這題就比較好解啦。。。。

code：

#include
#include
#include
#include
#include

using namespace std;

int a[450][450],b[450];   //a[i][j] 表示 i！中的素因子j的出現的次數
int prime[450],vis[450];
int len;
int primetable()         //打印素數表
{
    int i,j;
    int c=0;
    memset(vis,0,sizeof(vis));
    for(i=2;i<=431;i++)
    {
        if(!vis[i])
        {
            prime[c++]=i;
            for(j=i*i;j<=431;j+=i)
            {
                vis[j]=1;
            }
        }
    }
    return c;
}

void f()             //計算2！到431！中的每個數中的素因子的出現的次數
{
    int i,j;
    memset(a,0,sizeof(a));
    for(i=2;i<=431;i++)
    {
        int ii=i;
        memcpy(a[i],a[i-1],sizeof(a[i]));  //把a[i-1]中的各元素拷貝到a[i]中
        for(j=0;jii) break;
            if(ii%prime[j]==0)
            {
                int sum=0;
                while(ii%prime[j]==0)
                {
                    sum++;
                    ii/=prime[j];
                }
                a[i][prime[j]]+=sum;
            }
        }
    }
}

int main()
{
    int n,k,i,j;
    len=primetable();
    f();
    while(scanf(%d%d,&n,&k)==2)
    {
        memcpy(b,a[n],sizeof(a[n]));
        __int64 cnt=1;         //cnt用__int64，其他的變量用int就行啦
        for(i=0;i<=431;i++)
        {
            b[i]=b[i]-a[k][i]-a[n-k][i];
            cnt*=(1+b[i]);
        }
        printf(%I64d
,cnt);
    }
    return 0;
}