程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 2992-Divisors(求組合數質因子的個數)

POJ 2992-Divisors(求組合數質因子的個數)

編輯：C++入門知識

POJ 2992-Divisors(求組合數質因子的個數)

Divisors Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Submit Status Practice POJ 2992 Appoint description:

Description

Your task in this problem is to determine the number of divisors of C_n^k. 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 C_n^k. For the input instances, this number does not exceed 2 ⁶³ - 1.

Sample Input

5 1
6 3
10 4

Sample Output

2
6
16

題意：求C(n,m)的質因子的個數。

思路：知道公式很好做，不知道公式TLE到死，恰好我就是呢個不知道公式的，sad。

定理：設正整數n的所有素因子分解n=p1^a1*p2^a2*p3^a3****Ps^as,那麼T(n)=(a1+1)*(a2+1)*(a3+1)***(an+1);（求因子的個數的公式）

1.求出N以內素數

2.ei=[N/pi^1]+ [N/pi^2]+ …… + [N/pi^n] 其中[]為取整。即可以 int ei=0;while(N) ei+=(N/=pi);

3.套公式計算了，M=（e1+1）*（e2+1）*……*（en+1）

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
using namespace std;
typedef long long LL;
const int inf=0x3f3f3f3f;
const double pi= acos(-1.0);
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int prime[1010]= {2,3,5};
int k=3;
LL cnt[450][450];
void is_prime()
{
    int i,j;
    int flag=0;
    int gad=2;
    for(i=7; i<=1010; i+=gad) {
        flag=0;
        gad=6-gad;
        for(j=0; prime[j]*prime[j]<=i; j++) {
            if(i%prime[j]==0) {
                flag=1;
                break;
            }
        }
        if(!flag) {
            prime[k++]=i;
        }
    }
}

void get()
{
    is_prime();
    LL s,ret,i,j;
    for(i=2;i<=431;i++){
        for(j=0;prime[j]<=i;j++){
            s=i;
            ret=0;
            while(s){
                s=s/prime[j];
                ret+=s;
            }
            cnt[i][prime[j]]=ret;
        }
    }
}

int main()
{
    get();
    LL n,m,i;
    LL res,ans;
    while(~scanf("%lld %lld",&n,&m)){
        ans=1;
        for(i=0;prime[i]<=n;i++){
            res=cnt[n][prime[i]]-cnt[m][prime[i]]-cnt[n-m][prime[i]];
            ans*=(res+1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}