C2. No Cost Too Great (Hard Version)

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
#define all(x) begin(x), end(x)

template<typename T1, typename T2>
bool ckmin(T1& a, T2 b) {
    return a > b ? a = b, true : false;
}

template<typename T1, typename T2>
bool ckmax(T1& a, T2 b) {
    return a < b ? a = b, true : false;
}

const int nmax = 2e5;
const int valmax = 2e5 + 5;
int spf[valmax + 5];
vector<int> factors[valmax + 5];

int n;
int a[nmax + 5];
int b[nmax + 5];

void testcase() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
    }
    vector<int> ord(n);
    iota(all(ord), 1);
    sort(all(ord), [&](int i, int j) {
        return b[i] < b[j];
        });
    // am incercat operatii pe 2 numere
    long long answer = b[ord[0]] + b[ord[1]];
    map<int, int> occ;
    for (int i = 1; i <= n; ++i) {
        for (auto& p : factors[a[i]]) {
            if (occ[p] > 0) { // exista si altundeva factorul p
                answer = 0; // am incercat operatii pe 0 numere
            }
            occ[p]++;
        }
    }
    // mai ramane sa incerc sa fac pe un singur numar
    // incerc sa fac o singura operatie pe orice numar
    for (int i = 1; i <= n; ++i) {
        for (auto& p : factors[a[i]]) {
            occ[p]--;
        }
        for (auto& p : factors[a[i] + 1]) {
            if (occ[p] > 0) {
                ckmin(answer, b[i]);
            }
        }
        for (auto& p : factors[a[i]]) {
            occ[p]++;
        }
    }
    // incerc sa fac operatii pe cel mai ieftin numar
    for (auto& p : factors[a[ord[0]]]) {
        occ[p]--;
    }
    for (auto& it : occ) {
        if (it.second > 0) {
            int p = it.first;
            ckmin(answer, 1ll * (p - a[ord[0]] % p) % p * b[ord[0]]);
        }
    }
    cout << answer << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    for (int i = 1; i <= valmax; ++i) {
        spf[i] = i;
    }
    for (int i = 2; i * i <= valmax; ++i) {
        if (spf[i] == i) {
            for (int j = i * i; j <= valmax; j += i) {
                ckmin(spf[j], i);
            }
        }
    }
    for (int i = 1; i <= valmax; ++i) {
        int x = i;
        while (x > 1) {
            if (factors[i].empty() or factors[i].back() != spf[x]) {
                factors[i].push_back(spf[x]);
            }
            x /= spf[x];
        }
    }
    int tc = 1;
    cin >> tc;
    for (int t = 1; t <= tc; ++t) {
#ifdef _DEBUG
        cerr << "=== Subtask " << t << " ===\n";
#endif
        testcase();
#ifdef _DEBUG
        cerr << "\n";
#endif
    }
}