这题主要是质因数分解！！
求出每个因子的幂，如果有负数，则输出-1；
如果2的幂数为0，这输出0；
最后就是开始凑阶乘了……
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<iomanip> 5 #include<cmath> 6 #include<string> 7 #include<cstdlib> 8 #include<vector> 9 using namespace std; 10 int prime[1300],cnt,p[1300],q[1300],num[1300],len; 11 int s[1300],r[1300],a[1300]; 12 bool f[10010]; 13 int min(int a,int b) 14 { 15 return a>b?b:a; 16 } 17 int max(int a,int b) 18 { 19 return a>b?a:b; 20 } 21 void init() 22 { 23 int i,j; 24 cnt=0; 25 for(i=2;i<=10010;i++) 26 { 27 if(f[i]==0) prime[cnt++]=i; 28 for(j=0;j<cnt&&prime[j]*i<=10010;j++) 29 { 30 f[i*prime[j]]=1; 31 if(i%prime[j]==0) break; 32 } 33 } 34 } 35 int count(int n,int p)//计算n!中p因子的个数 36 { 37 int sum=0; 38 while(n>=p) 39 { 40 sum+=(n/=p); 41 } 42 return sum; 43 } 44 int divs(int n,int m)//分解因子 45 { 46 int i,j; 47 len=0; 48 memset(num,0,sizeof(num)); 49 for(i=0;i<n;i++) 50 { 51 for(j=0;prime[j]<=p[i];j++) 52 num[j]+=count(p[i],prime[j]); 53 len=max(len,j); 54 } 55 for(i=0;i<m;i++) 56 { 57 for(j=0;prime[j]<=q[i];j++) 58 { 59 if(j>=len) return -1; 60 num[j]-=count(q[i],prime[j]); 61 if(num[j]<0) return -1; 62 } 63 } 64 if(num[0]==0) return 0; 65 return 1; 66 } 67 int main() 68 { 69 init(); 70 int i,j,k,ans,n,m,temp,t,cur,mul; 71 bool flag; 72 cin>>t; 73 while(t--) 74 { 75 cin>>n>>m; 76 for(i=0;i<n;i++) cin>>p[i]; 77 for(i=0;i<m;i++) cin>>q[i]; 78 ans=divs(n,m); 79 if(ans<=0) 80 { 81 cout<<ans<<endl; 82 continue; 83 } 84 for(i=0;i<len&&num[i]>0;i++) ; 85 len=min(len,i); 86 cur=prime[i]-1; 87 cnt=0; 88 while(num[0]>0&&cur>=2) 89 { 90 flag=true; 91 a[0]=count(cur,prime[0]); 92 if(a[0]>num[0]) flag=false; 93 else mul=num[0]/a[0]; 94 for(i=1;flag&&i<len&&prime[i]<=cur;i++) 95 { 96 a[i]=count(cur,prime[i]); 97 if(a[i]>num[i]) flag=false; 98 else mul=min(mul,num[i]/a[i]); 99 } 100 if(flag && mul>0) 101 { 102 if(i<len) len=i; 103 r[cnt]=cur; 104 s[cnt++]=mul; 105 for(i=0;i<len;i++) 106 { 107 num[i]-=(mul*a[i]); 108 if(num[i]==0) break; 109 } 110 if(len>i) len=i,cur=prime[len]-1; 111 else cur--; 112 } 113 else cur--; 114 } 115 cout<<cnt<<endl; 116 for(i=0;i<cnt;i++) 117 cout<<r[i]<<' '<<s[i]<<endl; 118 } 119 return 0; 120 }