|
|
題目鏈接： 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;
}
|