减少整数分数算法 - 解决方案的说明？ [英] Reducing Integer Fractions Algorithm - Solution Explanation?
问题描述
这是一个随访对这一问题：
以下是从一个棋手一个解决问题的办法：
的#include＆LT; cstdio＆GT;
＃包括＆LT;算法＆GT;
的#include＆lt;功能＆GT;
使用名字空间std;
const int的MAXN = 100100;
const int的MAXP = 10001000;
INT P [MAXP]
无效的init（）{
的for（int i = 2; I＆LT; MAXP ++我）{
如果（第[I] == 0）{
对于（INT J =; J＆LT; MAXP; J + = 1）{
P [J] =我;
}
}
}
}
空隙F（INT N，矢量＆lt; INT＆GT;＆安培;一，矢量＆lt; INT＆GT;＆安培; x）的{
a.resize（N）;
矢量＆lt; INT＆GT;（MAXP，0）.swap（x）的;
的for（int i = 0;我n种; ++ I）{
scanf函数（％d个，和放大器; A [1]）;
为（中间体J = A [1]; J＆大于1;焦耳/ = P []]）{
+ X [P []]]
}
}
}
空隙克（常量矢量＆lt; INT＆GT;＆安培; V，矢量＆lt; INT＆GT; w）的{
对于（INT I：V）{
为（中间体J =; J＆大于1;焦耳/ = P []]）{
如果（瓦特[P [j]的]＆0）{
--w [P [J];
I / = P [J]。
}
}
的printf（％D，我）;
}
看跌期权（）;
}
诠释的main（）{
INT N，M;
矢量＆lt; int的＆GT;一个，B，X，Y，Z;
在里面（）;
scanf函数（％D，和放大器; N，放大器; M）;
F（N，A，X）;
F（M，B，y）基
的printf（％D \ N，N，M）;
变换（x.begin（），x.end（），y.begin（），
insert_iterator＆其中;矢量＆lt; INT＆GT; ＆GT;（Z，z.end（）），
[]（INT A，INT B）{返回分钟（A，B）; }）;
克（A，Z）;
G（B，Z）;
返回0;
}
这是我不清楚它是如何工作。任何人都可以解释一下吗？
的equivilance如下：
A是长度为n的分子载体
b是长度为m的分母矢量
的init 简单地填充阵列 P 等等该 P [I] 包含的最大素因子I 。
F（N，A，X）罢了 X 随着时代的数数的整除每一个素数，计算的力量多次。实际上，这台计算机的产品的质因子分解 A 。
G（V，W）取号的列表 v 和因式分解是W 并划分出V中的任何元素在w中一个共同的因素，直到他们共享没有共同的因素。 （分割的主要因子是指1减去功率）。
所以现在我们有主。首先，它初始化 P 阵列中的数据长度读取（奇怪的是它从来没有出现读取数据本身）。然后将其存储元件的产品在a和b的素因子分解在x和y分别。然后，它使用一个lambda EX pression在循环中采取元素明智的最低这两个因式分解，给人的最大公因数分解。最后，它划分出由本共同因子a和b的元素。
This is a followup to this problem:
Reducing Integer Fractions Algorithm
Following is a solution to the problem from a grandmaster:
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;
const int MAXN = 100100;
const int MAXP = 10001000;
int p[MAXP];
void init() {
for (int i = 2; i < MAXP; ++i) {
if (p[i] == 0) {
for (int j = i; j < MAXP; j += i) {
p[j] = i;
}
}
}
}
void f(int n, vector<int>& a, vector<int>& x) {
a.resize(n);
vector<int>(MAXP, 0).swap(x);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
for (int j = a[i]; j > 1; j /= p[j]) {
++x[p[j]];
}
}
}
void g(const vector<int>& v, vector<int> w) {
for (int i: v) {
for (int j = i; j > 1; j /= p[j]) {
if (w[p[j]] > 0) {
--w[p[j]];
i /= p[j];
}
}
printf("%d ", i);
}
puts("");
}
int main() {
int n, m;
vector<int> a, b, x, y, z;
init();
scanf("%d%d", &n, &m);
f(n, a, x);
f(m, b, y);
printf("%d %d\n", n, m);
transform(x.begin(), x.end(), y.begin(),
insert_iterator<vector<int> >(z, z.end()),
[](int a, int b) { return min(a, b); });
g(a, z);
g(b, z);
return 0;
}
It isn't clear to me how it works. Can anyone explain it?
The equivilance is as follows:
a is the numerator vector of length n
b is the denominator vector of length m
init simply fills the array P so that P[i] contains the largest prime factor of i.
f(n,a,x) fills x with the number of times a number in a is divisible by each prime, counting powers multiple times. In effect it computers the prime factorization of the product of a.
g(v,w) takes a list of numbers v and a prime factorization w and divides out any element in v with a common factor in w until they share no common factors. (Dividing the prime factorization means subtracting the power by 1).
So now we have main. First it initializes the P array and reads in the data lengths (strangely it never appears to read in the data itself). Then it stores the prime factorizations of the products of elements in a and b in x and y respectively. Then it uses a lambda expression in a loop to take the element wise minimum of these two factorizations, giving the factorization of the greatest common factor. Finally it divides out elements in a and b by this common factor.
这篇关于减少整数分数算法 - 解决方案的说明？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
