M.J的blog

先說一個定理：

        若正整數n可分解為p1^a1*p1^a2*...*pk^ak
        其中pi為兩兩不同的素數,ai為對應指數
        n的約數個數為(1+a1)*(1+a2)*....*(1+ak)
        如180=2*2*3*3*5=2^2*3^2*5
       180的約數個數為(1+2)*(1+2)*(1+1)=18個。

       若求A/B的約數個數，A可分解為p1^a1*p2^a2*...*pk^ak，B可分解為q1^b1*q1^b2*...*qk^bk,則A/B的約數個數            為(a1-b1+1)*(a2-b2+1)*(a3-b3+1)...*(ak-bk+1).

然后說N的階乘：

例如:20!
1.先求出20以內的素數,(2,3,5,7,11,13,17,19)
2.再求各個素數的階數
e(2)=[20/2]+[20/4]+[20/8]+[20/16]=18;
e(3)=[20/3]+[20/9]=8;
e(5)=[20/5]=4;
...
e(19)=[20/19]=1;
所以
20!=2^18*3^8*5^4*...*19^1

解釋：
2、4、6、8、10、12、14、16、18、20能被2整除
4、8、12、16、20能被4整除（即被2除一次后還能被2整除）
8、16能被8整除（即被2除兩次后還能被2整除）
16能被16整除（即被2除三次后還能被2整除）
這樣就得到了2的階。其它可以依次遞推。

所以在求N的階乘質數因數個數時，從最小的質數開始，

1int cal(int n, int p) {
2     if(n < p) return 0;
3     else return n / p + cal(n / p, p);
4}

下面附上TOJ 2308的AC代碼：

#include<iostream>
#include<cmath>
using namespace std;
#define N 90
#define M 450  
int p[M+2]={0};
int prime[N+2],l,q,t=1;          //求前90個素數
void getprime(int n)
{
   for(l=2;l<n;l++)
   {
       if(!p[l])
       {
            for(q=l+l;q<n;q+=l)
            {
                p[q]=1;
            }
            prime[t]=l;t++;
       }
   }
}
int cal(int n,int m)   //求N的階乘含質因數M的次數
{
   if(m>n)
      return 0;
   else
      return n/m+cal(n/m,m);
}
int main()
{
   int i,j,k,n;
   long long m;
   getprime(M);
   while(cin>>n>>k)
   {
      if(2*k>n)  k=n-k;
      for(i=1,m=1;prime[i]<=n,i<t;i++)
          m*=(cal(n,prime[i])-cal(k,prime[i])-          cal(n-k,prime[i])+1);  
      cout<<m<<endl;
   
   }
}