CF222C Reducing Fractions

题目大意：

给出两个集合，第一个集合数的乘积是分子，第二个集合的数的乘积是分母，要求够造一个同样的集合，但是得到的分数是最简分数。

分析：

寻找思路并不复杂，对两个集合的每个数进行质因数分解，然后统计整个集合的质因数分解情况，再将两个集合的质因数的次数大减小即可。构造时使两个集合中元素的个数不变，尽可能地构造成原先集合的数，如果不行就填一个 \(1\)。但质因数分解的过程中不能采用 \(O(\sqrt n)\) 的复杂度，会超时，接下来介绍本题中进行质因数分解的方法。

其实也不是很复杂，就是对于每个被分解的数，优先除以它最大的质因数即可。当然，需要提前处理一下每个数最大的质因数。

AC代码：

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int M = 1e7;

const int MAXN = 1e4;

int n,m;

map<int,int> cnt1,cnt2;

set<int> s;

int prime[M + 5],up[M + 5],down[M + 5],a[M + 5],bb[M + 5];

signed main(){

   //freopen("B.out","r",stdin);

   //prime.push_back(9999991);

   for(int i = 2; i <= M; i++){//预处理每个数的最大质因数

       if(prime[i] == 0){

       	prime[i] = i;

       	for(int j = i + i; j <= M + 3; j+=i){

       		prime[j] = i;

   		}

   	}

   }

   cin >> n >> m;

   for(int i = 1; i <= n; i++){

       cin >> a[i];

       int j;

   	for(j = a[i]; j > 1; j /= prime[j]){//质因数分解

  			s.insert(prime[j]);

   		up[prime[j]]++;//存储分子的质因数分解情况

   	}

   }

   for(int i = 1; i <= m; i++){

       cin >> bb[i];

       int j;

   	for(j = bb[i]; j > 1; j /= prime[j]){//质因数分解

  			s.insert(prime[j]);

   		down[prime[j]]++;//存储分母的质因数分解情况

   	}

   }

   int b;

   int now = 1;

   cout << n << " " << m << "\n";

   for(int i = 1; i <= n; i++){

   	int j;

   	int tmp  =1;

   	for(j = a[i]; j > 1; j /= prime[j]){

   		if(down[prime[j]] > 0){

   			down[prime[j]]--;//如果当前该数的质因数能在分母里也含油1，那么就将它约去，否则将它乘到答案里面

   		}

   		else{

   			tmp *= prime[j];

   		}

   	}

   	cout << tmp << " ";

   }

   puts("");

   for(int i = 1; i <= m; i++){

   	int j;

   	int tmp = 1;

   	for(j = bb[i]; j > 1; j /= prime[j]){

   		if(up[prime[j]] > 0){

   			up[prime[j]]--;//同上

   		}

   		else{

   			tmp *= prime[j];

   		}

   	}

   	cout << tmp << " ";

   }

   return 0;

}

巴特西

CF222C Reducing Fractions

题目大意：

分析：

AC代码：

最新文章

热门文章