|
|
题目链接： 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, 0, sizeof(c));
for(i = 0; i < n; i++) {
scanf("%d", &p[i]);
add(1, 1);
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, 0, sizeof(c));
bool flag = true;
for(i = 0; i < m; i++) {
scanf("%d", &q[i]);
add(1, 1);
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;
}
|