随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

HDU 3758 Factorial Simplification

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3758
/*
题意:
    给定N个和M个不大于10000的数(N,M <= 1000),N个数各自的阶乘的乘积
除上M个数各自阶乘的乘积是一个很大的数,现在要求将这个数表示成如下形
式:
    r1!^s1 * r2!^s2 *  * rk!^sk * t
    并且要求r1最大,相同情况下满足s1最大;相同情况下满足r2最大
此类推,最后输出(ri,si)(1 <= i <= k)。

题解:
    素因子分解

思路:
    首先我们要确定r1的范围,因为所有的数都是在10000以内的,那么是否
r1的范围就是2到10000呢?答案是否定的,来考虑10002这个数,他等于5001
*2,那么如果原来的数的最后结果有5001,必然能将10002凑出来,所以r1可
以大于10000,那么最大的情况是多少呢,答案是10006,因为10007是10000
以上第一个素数,他不能被10000以下所有的数整除。
    确定了r1的范围后,再来考虑如何将输入的那么大的数表示出来,可以
采用素因子分解,10006以内有1200多个素数,将N个数分别进行素因子分解
,这里注意的是每个数实际表示的是它的阶乘,所以对于每个数X,首先要枚
举比它小的素数,然后采用logp(X)的分解方法,因为对于阶乘的素因子X的
素因子个数F(X, P) = X/P + F(X/P, P),这题时间卡的比较紧,最好不要用
递归,也可以把F(X, P)事先预处理出来。
    分别将N个数和M个数的素因子分解后,将前者所有素因子数目减去后者所
有素因子数目,最后判每个素因子的个数,如果一旦有一个小于零,说明原来
的数不是一个整数,直接输出-1。否则进行拆分。
    拆分过程是暴力做的,从10006开始枚举,对于每个r1,r1的阶乘的每个
素因子个数和原先素因子个数取一个大的,最后如果这个值不为零,说明s1
就是那个数,这个是很明显的,如果找到这样的s1,同时也找到了最大的r1,
然后将各个素因子减去,继续递归做下一层。
*/

#include 
<iostream>
#include 
<vector>
using namespace std;

#define maxn 10011
#define maxm 802

bool f[maxn];
int prime[maxn], size;
int prime_idx[maxn];

struct PrimeFactor {
    
short num;    // 素因子数量
    short pri;    // 素因子在prime[]的下标
    PrimeFactor() {}
    PrimeFactor(
int _n, int _p) {
        num 
= _n;
        pri 
= _p;
    }

}
;
vector 
< PrimeFactor > PriFac[maxn];
int preAns[maxn][maxm];

int DFS(int n, int p) {
    
if(p < maxm)
        
return preAns[n][p];
    p 
= prime[p];
    
int s = 0;
    
while(n >= p) {
        
int tmp = n / p;
        s 
+= tmp;
        n 
= tmp;
    }

    
return s;
}


void Init() {
    
int i, j;
    
for(i = 2; i < maxn; i++{
        
if(!f[i]) {
            PriFac[i].push_back(PrimeFactor(
1, size));
            
for(j = i+i; j < maxn; j += i) {
                f[j] 
= 1;

                PrimeFactor pf;
                pf.num 
= 1;
                pf.pri 
= size;
                
int v = j / i;

                
while(!(v % i)) {
                    v 
/= i;
                    pf.num 
++;
                }

                PriFac[j].push_back(pf);
            }

            prime[size] 
= i;
            prime_idx[i] 
= size;
            
            size
++;
        }

    }


    
int nCount = 0;
    
for(i = 2; i <= 10006; i++{
        
for(j = 0; j < PriFac[i].size(); j++{
            
if(PriFac[i][j].pri < maxm)
                preAns[i][ PriFac[i][j].pri ] 
= PriFac[i][j].num;
        }

        
for(j = 0; j < maxm; j++)
            preAns[i][j] 
+= preAns[i-1][j];
    }

}


int n, m;
int prime_num[maxn];
int tmp_num[maxn];

vector 
< PrimeFactor > vecAns;

int Min(int a, int b) {
    
return a < b ? a : b;
}


void Calc(int nMax) {
    
int i, j;
    
int MaxDeg = INT_MAX;
    
for(i = nMax; i >= 2; i--{
        MaxDeg 
= INT_MAX;
        
for(j = 0; j < size && prime[j] <= i; j++{
            
if(DFS(i, j)) 
                MaxDeg 
= Min(MaxDeg, prime_num[j] / DFS(i, j));
            
if(MaxDeg == 0)
                
break;
        }


        
if(MaxDeg) {
            
break;
        }

    }


    
if(i >= 2{
        nMax 
= i;
        vecAns.push_back(PrimeFactor(MaxDeg, nMax));
        
for(i = 0; i < size && prime[i] <= nMax; i++{
            prime_num[i] 
-= MaxDeg * DFS(nMax, i);
        }

        
if(nMax > 2)
            Calc(nMax 
- 1);
    }

}


int p[maxn], q[maxn];
int c[20 + maxn];
int lowbit(int x) {
    
return x & (-x);
}


int sum(int pos) {
    
int s = 0;
    
while(pos > 0{
        s 
+= c[pos];
        pos 
-= lowbit(pos);
    }

    
return s;
}


void add(int pos, int v) {
    
while(pos < maxn) {
        c[pos] 
+= v;
        pos 
+= lowbit(pos);
    }

}


int main() {
    Init();
    
int t, i, j;
    scanf(
"%d"&t);
    
while(t--{
        scanf(
"%d %d"&n, &m);
        
for(i = 0; i < size; i++)
            prime_num[i] 
= 0;
            
        memset(c, 
0sizeof(c));
        
for(i = 0; i < n; i++{
            scanf(
"%d"&p[i]);
            add(
11);
            add(p[i]
+1-1);
        }

        
for(i = 2; i <= 10000; i++{
            
int v = sum(i);
            
if(v) {
                
for(j = 0; j < PriFac[i].size(); j++{
                    prime_num[ PriFac[i][j].pri ] 
+= PriFac[i][j].num * v;
                }

            }

        }


        memset(c, 
0sizeof(c));
        
bool flag = true;
        
for(i = 0; i < m; i++{
            scanf(
"%d"&q[i]);
            add(
11);
            add(q[i]
+1-1);
        }


        
for(i = 2; i <= 10000; i++{
            
int v = sum(i);
            
if(v) {
                
for(j = 0; j < PriFac[i].size(); j++{
                    prime_num[ PriFac[i][j].pri ] 
-= PriFac[i][j].num * v;
                    
if(prime_num[ PriFac[i][j].pri ] < 0{
                        flag 
= false;
                        
break;
                    }

                }

            }

            
if(!flag)
                
break;
        }



        
if(!flag) {
            printf(
"-1\n");
        }
else {
            vecAns.clear();
            Calc(
10006);
            
            printf(
"%d\n", vecAns.size());
            
for(i = 0; i < vecAns.size(); i++{
                printf(
"%d %d\n", vecAns[i].pri, vecAns[i].num);
            }

        }

    }


    
return 0;
}

posted on 2011-04-15 09:11 英雄哪里出来 阅读(450) 评论(0)  编辑 收藏 引用 所属分类: 数学


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理