t3

using ll = long long;
vector<int> primes, not_prime, prime_factor;

class Solution {
    static void get_prime(int n) {
        if (primes.size())
            return;
        not_prime = vector<int>(n + 1);
        prime_factor = vector<int>(n + 1);
        for (int i = 2; i <= n; ++i) {
            if (!not_prime[i]) {
                primes.push_back(i);
                prime_factor[i] = i;
            }
            for (int j = 0; j < primes.size() && primes[j] * i <= n; ++j) {
                not_prime[i * primes[j]] = 1;
                prime_factor[i * primes[j]] = primes[j];
                if (i % primes[j] == 0)
                    break;
            }
        }
    }
public:
    long long numberOfPairs(vector<int>& ns1, vector<int>& ns2, int k) {
        ll ret = 0;
        vector<int> ns3;
        for (auto x: ns1)
            if (x % k == 0)
                ns3.push_back(x / k);
        map<int, int> ns2cnt;
        for (auto x: ns2) ns2cnt[x] += 1;
        sort(ns3.begin(), ns3.end());
        map<int, set<int>> ns3set;
        for (auto x: ns3) {
            if (ns3set.count(x))
                continue;
            for (int i = 1; i * i <= x; ++i)
                if (x % i == 0)
                    ns3set[x].insert(x / i), ns3set[x].insert(i);
        }
        for (auto x: ns3)
            for (auto f: ns3set[x])
                ret += ns2cnt[f];
        return ret;
    }
    long long numberOfPairs1(vector<int>& ns1, vector<int>& ns2, int k) {
        constexpr int ub = 1e6 + 3;
        get_prime(ub);

        ll ret = 0;
        vector<int> ns3;
        for (auto x: ns1)
            if (x % k == 0)
                ns3.push_back(x / k);
        vector<int> ns2cnt(ub);
        for (auto x: ns2) ns2cnt[x] += 1;
        for (auto p: primes)
            for (int i = 1; i * p < ub; ++i)
                ns2cnt[i * p] += ns2cnt[i];

        for (auto x: ns3)
            ret += ns2cnt[x];
        return ret;
    }
};