欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C. Reducing Fractions

程序员文章站 2022-06-08 12:23:56
...

题目链接:http://codeforces.com/group/NVaJtLaLjS/contest/238985/problem/C4

题面:

C. Reducing Fractions

C. Reducing Fractions 

题目描述:给你两个数组,一个数组乘起来是分子的乘积,一个数组乘起来是分母的乘积,问最后把他化成两个没有公共因子的两个数组结果是什么 ?输出其中一种。

题解:先对两个数组质因数分解,然后互相约掉公因子即可。学习到一个很好的质因数分解的方法,记录每个数最大的质因子,就可以很快的对那个数进行质因数分解。

代码:

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e7+7;
const int maxnn = 1e5+7;
int prime[maxn];
int row[maxnn],col[maxnn];
int up[maxn],down[maxn];

void init(){
	for(int i = 2;i <= 10000000; i++){
		if(!prime[i]){
			prime[i] = i;
			for(int j = i+i;j <= 10000000; j += i){
				prime[j] = i;
			}
		}
	}
}


int main(){
	int n,k;
	cin >> n >> k;
	init();
	for(int i = 1;i <= n; i++)scanf("%d",&row[i]);
	for(int i = 1;i <= k; i++)scanf("%d",&col[i]);
	for(int i = 1;i <= n; i++){
		for(int j = row[i];j > 1; j /= prime[j]){
			up[prime[j]]++;
		}
	}
	for(int i = 1;i <= k; i++){
		for(int j = col[i];j > 1; j /= prime[j]){
			down[prime[j]]++;
		}
	}
	printf("%d %d\n",n,k);
	for(int i = 1;i <= n; i++){
		int tmp = 1;
		for(int j = row[i];j > 1; j /= prime[j]){
			if(down[prime[j]] > 0)down[prime[j]]--;
			else tmp *= prime[j];
		}
		printf("%d ",tmp);
	}
	puts("");
	for(int i = 1;i <= k; i++){
		int tmp = 1;
		for(int j = col[i];j > 1; j /= prime[j]){
			if(up[prime[j]] > 0)up[prime[j]]--;
			else tmp *= prime[j];
		}
		printf("%d ",tmp);
	}
	return 0;
}