HDU 3758 Factorial Simplification - c++编程基础

数论。题目要求把一个阶乘式化简成另一个阶乘式。

首先，对于第一个阶乘式我们要判断式子算出来是不是整数，第二问是如果是整数的话能否分解成第二种阶乘式的形式，系数t不用考虑，如果能的话输出第二种阶乘式。对于第一问，因为q和p都比较小，只有10000的样子，这样的话我们可以分别统计一下分子分母中每个数字都出现了多少次，然后把所有的数字都质分解，因为这样的分子分母都成为了质因数相乘的形式，然后我们比较一下能否除尽就可以了。

然后就是第二问了，对于第二问由于题目要求的是r1，s1都尽量大，这样的话，只要贪心的求出最大的r1，s1，然后继续求着下去就可以了。对于r 我们很容易知道r是大于等于2的，因为题目说了。因为想到p是不超过10000的，所以10007这个质数的阶乘数是无法形成的，r的上界就可以确定了。因为数据比较小，就算是最大的数据，对于枚举时间复杂度也是可以接受的。所以我就枚举了。。。不过第二问是可以预处理出阶乘的质因子，然后二分求的，那样可能会快一些，我这样枚举的确非常慢。。。不过ac还是没问题的。

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#define REP(i, n) for(int i=0; i hav[N], p;  
bool isp[N];  
int c[2][N], q[N];  
int ans[N];  
  
void init()  
{  
    CLR(isp, true);  
    isp[0] = isp[1] = false;  
    for(int i = 2; i < N; i ++) if(isp[i])  
    {  
        p.push_back(i);  
        for(int j = i * i; j < N; j += i)  
        {  
            isp[j] = false;  
        }  
    }  
    hav[1].push_back(1);  
    for(int i = 2; i < N; i ++)  
    {  
        for(int j = 0, x = i; x > 1; j ++)  
        {  
            while(x % p[j] == 0)  
            {  
                hav[i].push_back(p[j]);  
                x /= p[j];  
            }  
        }  
    }  
    return ;  
}  
  
void add(int x, int ad, int id)  
{  
    while(x < N)  
    {  
        c[id][x] += ad;  
        x += x & (-x);  
    }  
    return ;  
}  
  
int sum(int x, int id)  
{  
    int ret = 0;  
    while(x)  
    {  
        ret += c[id][x];  
        x -= x & (-x);  
    }  
    return ret;  
}  
  
int t, n, m, k, big[2];  
  
void input()  
{  
    int x;  
    scanf("%d%d", &n, &m);  
    CLR(c, 0);CLR(q, 0);CLR(big, 0);  
    REP(i, n)  
    {  
        scanf("%d", &x);  
        add(1, 1, 0);  
        add(x + 1, -1, 0);  
        big[0] = max(big[0], x);  
    }  
    REP(i, m)  
    {  
        scanf("%d", &x);  
        add(1, 1, 1);  
        add(x + 1, -1, 1);  
        big[1] = max(big[1], x);  
    }  
    return ;  
}  
  
void solve()  
{  
    bool flag = false;  
    for(int k = 0; k < 2; k ++)  
        for(int i = 2; i <= big[k]; i ++)  
        {  
            int num = sum(i, k);  
            for(int j = 0; j < hav[i].size(); j ++)  
            {  
                int idx = hav[i][j];  
                q[idx] += num * ((k & 1)   -1 : 1);  
                if(q[idx] < 0)  
                {  
                    puts("-1");  
                    return ;  
                }  
            }  
        }  
    if(!q[2])  
    {  
        puts("0");  
        return ;  
    }  
    CLR(ans, 0);  
    while(q[2])  
    {  
        for(int i = 2; i <= 10007; i ++)  
        {  
            int sit = -1;  
            for(int j = 0; j < hav[i].size(); j ++)  
            {  
                int tmp = hav[i][j];  
                q[tmp] --;  
                if(q[tmp] < 0)  
                {  
                    sit = j;  
                    break;  
                }  
            }  
            if(sit != -1)  
            {  
                for(int j = 0; j <= sit; j ++)  
                {  
                    int tmp = hav[i][j];  
                    q[tmp] ++;  
                }  
                ans[i - 1] ++;  
                break;  
            }  
        }  
    }  
    k = 0;  
    for(int i = 2; i <= 10007; i ++)  
    {  
        if(ans[i]) k ++;  
    }  
    printf("%d\n", k);  
    for(int i = 10007; i >




= 2; i --)  
    {  
        if(ans[i]) printf("%d %d\n", i, ans[i]);  
    }  
}  
  
int main()  
{  
    init();  
    scanf("%d", &t);  
    while(t --)  
    {  
        input();  
        solve();  
    }  
    return 0;  
}