Nk 1430 Divisors（因子数与质因数）

Time Limit: 5000 ms Memory Limit: 10000 kB
Total Submit : 432 (78 users) Accepted Submit : 108 (57 users) Page View : 3479 Font Style: Aa Aa Aa
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 263 - 1.
Sample Input
5 1
6 3
10 4Sample Output
2
6
16

代码如下：12=2^2*3^1 因子个数就等于（2+1）*（1+2）=12

#include<iostream>

#include<cstdio>

using namespace std;

int num;

bool a[];

struct prime

{

    int num;

    int count;

}p[];

void init()

{

    int i,j;

    memset(a,true,sizeof(a));

    num=;

    for(i=;i<;i++)

    {

        if(a[i]) p[num++].num=i;

        for(j=;j<num&&i*p[j].num<;j++)

        {

            a[p[j].num*i]=;

            if(i%p[j].num==)

                break;

        }

    }

}

__int64 Deal(int n,int m)

{

    int i,j;

    int a,b;

    __int64 sum=;

    if(m*<n)

        a=n,b=n-m;

    else

        a=n,b=m;

    for(i=;i<num;i++)

        p[i].count=;

    for(i=b+;i<=a;i++)

    {

        int t=i;

        for(j=;p[j].num<=i && j<num && t!=;j++)

        {

            while(t%p[j].num==)

            {

                t/=p[j].num;

                p[j].count++;

            }

        }

    }

    for(i=;i<=a-b;i++)

    {

        int t=i;

        for(j=;p[j].num<=i && j<num && t!=;j++)

        {

            while(t%p[j].num==)

            {

                t/=p[j].num;

                p[j].count--;

            }

        }

    }

    for(i=;i<num;i++)

    {

        if(p[i].count)

            sum*=(p[i].count+);

    }

    return sum;

}

int main()

{

    int n,m;

    init();

    while(cin>>n>>m)

        printf("%I64d\n",Deal(n,m));

    return ;

}

巴特西

Nk 1430 Divisors（因子数与质因数）

最新文章

热门文章