C. Reducing Fractions
程序员文章站
2022-06-08 12:23:56
...
题目链接:http://codeforces.com/group/NVaJtLaLjS/contest/238985/problem/C4
题面:
题目描述:给你两个数组,一个数组乘起来是分子的乘积,一个数组乘起来是分母的乘积,问最后把他化成两个没有公共因子的两个数组结果是什么 ?输出其中一种。
题解:先对两个数组质因数分解,然后互相约掉公因子即可。学习到一个很好的质因数分解的方法,记录每个数最大的质因子,就可以很快的对那个数进行质因数分解。
代码:
#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;
}
推荐阅读
-
c. 求阶乘和的方法(N的值不能太大)初学者
-
C.进程调度实例讲解
-
codeforces C. Count Triangles
-
Codeforces 1355 C. Count Triangles
-
codeforces C. K-th Not Divisible by n
-
Robert C. Martin对RoR的高度评价令我吃惊
-
CodeForces - 1089F Fractions (同余方程,互质数)
-
VK Cup 2017 - Qualification 1 C. Cycle In Maze(bfs+最短路+贪心+思维)
-
VK Cup 2017 - Qualification 2 C. Online Courses In BSU(dfs)
-
Codeforces Round #320 (Div. 2) C. A Problem about Polyline ( 数学 )