Reducing Fractions

Created by LXC on Mon Jun 26 09:05:09 2023

https://codeforces.com/problemset/problem/222/C

ranting: 1800

tag: implementation, math, number theory, sortings

problem

有一个分数，用n个数的数组a的乘积表示分子，用m个数的数组b的乘积表示分母。

现在需要构造一个化简的分数。其由$n_{out}$个数组成的分子，和$m_{out}$个数组成的分母。

$n_{out}$与$m_{out}$由你决定。只是要保证表示分子的$n_{out}$个数的乘积与表示分母的$m_{out}$个数的乘积互质。

$1 \le n,m \le 10^5$

$1 \le a_i,b_i \le 10^7$

solution

给出的内存限制 256 megabytes。

256 * 1024 * 1024 = 268435456 bytes

int数据类型默认4字节，268435456/4 = 67108864。

所以我们可以开6个长度为$10^7$的int型数组。

解题思路是先求出分子的n个数的质因数及其个数。同样也求出分子的m个数的质因数及其个数。

设$ap_i$为a中分解质因数后质数i的个数，设$bp_i$为b中分解质因数后质数i的个数。

为了保证分子分母互质，那么分子分母中需要去除公共的质数个数，对于$a_i$和$b_i$都需要去除$max(a_i, b_i)$，我们挑选a和b中一些包含多余质因子的数除去这些质因子。最后两个数组的长度不变，但是其分别的乘积互质。

具体做法

利用线性筛花费$O(N)$的时间与空间，求出N以内每个数i的最小质因数，即得到数组lpf，$lpf_i$为i的最小质因数。利用lpf可以$O(log (a_i))$时间分解出$a_i$的质因数。那么两个数组分解质因数所需时间$O((m+n)log(N))$。将每个数组的多余质因数去除，需要再次分解质因数寻找数组中包含多余质数的元素。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
#define MAXN 10000007
using namespace std;

vector<int> p;
int lpf[MAXN];  // lpf[i] i的最小质因子
int ap[MAXN], bp[MAXN];

void least_prime_factor(int n) {  // 求n及以内的所有数的最小质因子
    for (int i = 2; i <= n; i++) {
        if (lpf[i] == 0) {
            p.push_back(i);
            lpf[i] = i;
        }
        for (int j = 0; 1LL * p[j] * i <= n; j++) {
            lpf[p[j] * i] = p[j];
            if (i % p[j] == 0)
                break;
        }
    }
    lpf[1] = 1;
    // for (int i = 1; i <= n; i++) {
    //     // cout << i << " " << lpf[i] << endl;
    //     cout << lpf[i] << " ";
    // }
    // cout << "\n";
}

void sol() {
    least_prime_factor(MAXN - 1);
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (auto& i : a) {
        cin >> i;
        int x = i;
        for (; lpf[x] != 1; x /= lpf[x]) {
            ap[lpf[x]]++;
        }
    }
    for (auto& i : b) {
        cin >> i;
        int x = i;
        for (; lpf[x] != 1; x /= lpf[x]) {
            bp[lpf[x]]++;
        }
    }
    for (auto i : p) {
        ap[i] = bp[i] = min(ap[i], bp[i]);
    }
    for (auto& i : a) {
        int x = i;
        for (; lpf[x] != 1; x /= lpf[x]) {
            if (ap[lpf[x]] > 0) {
                ap[lpf[x]]--;
                i /= lpf[x];
            }
        }
    }
    for (auto& i : b) {
        int x = i;
        for (; lpf[x] != 1; x /= lpf[x]) {
            if (bp[lpf[x]] > 0) {
                bp[lpf[x]]--;
                i /= lpf[x];
            }
        }
    }
    cout << n << " " << m << "\n";
    for (auto i : a) {
        cout << i << " ";
    }
    cout << "\n";
    for (auto i : b) {
        cout << i << " ";
    }
    cout << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}