【（阶乘的质因数分解）算组合数】【TOJ4111】【Binomial efficient】-白红宇

【（阶乘的质因数分解）算组合数】【TOJ4111】【Binomial efficient】

阅读量：6125 次

发布时间：2019-06-21

本文共 3119 字，大约阅读时间需要 10 分钟。

n<=10^6

m<=10^6

p=2^32

用unsigned int 可以避免取模

我写的SB超时阶乘分解代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #define oo 0x13131313using namespace std;const unsigned int N=1000000+5;unsigned int tag[N],p[N],z[N],mm[N];unsigned int cnt = 0;unsigned int n,m;unsigned int quickpow(unsigned int m,unsigned int n){ unsigned int b = 1; while (n > 0) { if (n & 1) b = (b*m); n = n >> 1 ; m = (m*m); } return b;}void get_prime(){ tag[1]=1; tag[0]=1; for (unsigned int i = 2; i < N; i++) { if (!tag[i]) p[cnt++] = i; for (unsigned int j = 0; j < cnt && p[j] * i < N; j++) { tag[i*p[j]] = 1; if (i % p[j] == 0) break; } }}unsigned int FIND(unsigned int x){ unsigned int l=0,r=cnt-1; while(l<=r) { unsigned int m=(l+r)/2; if(p[m]==x) return m; else if(p[m]
             
              >T; while(T--) { cin>>n>>m; memset(z,0,sizeof(z)); memset(mm,0,sizeof(mm)); for(unsigned int i=n;i>=n-m+1;i--) fenjie(z,i); for(unsigned int i=1;i<=m;i++) fenjie(mm,i); unsigned int ans=1; for(unsigned int i=0;i

利用阶乘的质因数分解！

比如２５０！

１＊２＊３＊４＊５＊６＊７＊８＊９＊１０＊１１＊１２＊１３＊１４．．．．．２５０

中３的质因子个数　除了３后变成（不是倍数的不管）计算３＾１次方的为２５０／３个

又变成　１　２　３　．．．．．２５０除３　　

重复上面　知道　３＾２　为２５０／（３＾２）　

所以阶乘的质因数分解是另外的简单算法

void getcn(int n){	int ans = 0;	int i;	for (i = 1; i <= prime[0] && prime[i] <= n; i++)	{		int tmp = n;		while (tmp)		{			num[i] += tmp / prime[i];			tmp /= prime[i];		}	}	num[0] = i;}

所以最后的代码是

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #include 
                  
                   #define INF 0x3f3f3f3f#define MAXN 1000005#define Precision 100005#define MAX_INT 2147483647#define Pi acos(-1.0)#define lowbit(x) ((x)&(-x))#define Lson root<<1,left,mid#define Rson root<<1|1,mid+1,right#define LL long long#define ULL unsigned long long#define fresh(x) memset(x,0,sizeof(x))using namespace std;int prime[MAXN];int num[MAXN];void print(){
                    memset(prime, 0, sizeof(prime));
                    for (int i = 2; i <= 1000000; i++)
                    {
                    if (!prime[i]) prime[++prime[0]] = i;
                    for (int j = 1; j <= prime[0] && prime[j] <= 1000000 / i; j++)
                    {
                    prime[prime[j]*i] = 1;
                    if (i % prime[j] == 0) break;
                    }
                    }}unsigned qpow(unsigned a, unsigned b){
                    unsigned ans = 1;
                    while (b)
                    {
                    if (b & 1)
                    ans *= a;
                    b >>= 1;
                    a *= a;
                    }
                    return ans;}void getcn(int n){
                    int ans = 0;
                    int i;
                    for (i = 1; i <= prime[0] && prime[i] <= n; i++)
                    {
                    int tmp = n;
                    while (tmp)
                    {
                    num[i] += tmp / prime[i];
                    tmp /= prime[i];
                    }
                    }
                    num[0] = i;}void getcm(int m){
                    int ans = 0;
                    int i;
                    for (i = 1; i <= prime[0] && prime[i] <= m; i++)
                    {
                    int tmp = m;
                    while (tmp)
                    {
                    num[i] -= tmp / prime[i];
                    tmp /= prime[i];
                    }
                    }}int main(){
                    int n, m, T;
                    print();
                    //printf("%d\n", prime[prime[0]]);
                    //cout << prime[0];
                    scanf("%d", &T);
                    while (T--)
                    {
                    memset(num, 0, sizeof(num));
                    scanf("%d%d", &n, &m);
                    getcn(n);
                    getcm(m);
                    getcm(n - m);
                    unsigned ans = 1;
                    for (int i = 1; i <= num[0]; i++)
                    {
                    ans *= qpow(prime[i], num[i]);
                    }
                    printf("%u\n", ans);
                    }
                    return 0;}