POJ 2992-Divisors(求组合数质因子的个数) - c++编程基础

TOP

POJ 2992-Divisors(求组合数质因子的个数)

2015-11-21 01:03:33 来源: 作者: 【大中小】浏览:1次

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; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：Delete HDU5210 （模拟贪心）	下一篇：SDUT 3165 Round Robina（模拟）

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: