HackerRank Number Theory – Unfriendly Numbers

Challenge: Unfriendly Numbers

Subdomeniu: Number Theory (number-theory)

Scor cont: 80.0 / 80

Submission status: Accepted

Submission score: 1.0

Submission ID: 464759939

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/unfriendly-numbers/problem

Cerinta

Given $1$ *friendly* number and $n$ *unfriendly* numbers, determine how many numbers are divisors of the friendly number but *not* the unfriendly numbers.

Input Format

The first line contains $2$ space-separated integers, $n$ (the number of unfriendly numbers) and $f$ (the friendly number), respectively. 
The second line contains $n$ space-separated unfriendly numbers.

Output Format

Print the the number of unique divisors of $f$ (i.e.: divisors that are not shared with those of the unfriendly numbers) as a single integer.

Constraints

- $1 \le n \le 10^6$
- $1 \le f \le 10^{13}$
- $1 \le \textit{unfriendly numbers} \le 10^{18}$

Cod sursa

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    int64 f;
    cin >> n >> f;

    // Factorize f.
    vector<pair<int64, int>> pf;
    int64 x = f;
    for (int64 p = 2; p * p <= x; ++p) {
        if (x % p == 0) {
            int e = 0;
            while (x % p == 0) {
                x /= p;
                ++e;
            }
            pf.push_back({p, e});
        }
    }
    if (x > 1) pf.push_back({x, 1});

    // Generate all divisors of f.
    vector<int64> divisors;
    function<void(int, int64)> genF = [&](int idx, int64 cur) {
        if (idx == (int)pf.size()) {
            divisors.push_back(cur);
            return;
        }
        auto [p, e] = pf[idx];
        int64 val = 1;
        for (int i = 0; i <= e; ++i) {
            genF(idx + 1, cur * val);
            val *= p;
        }
    };
    genF(0, 1);

    unordered_set<int64> gset;
    gset.reserve(n * 2 + 1);

    for (int i = 0; i < n; ++i) {
        int64 u;
        cin >> u;
        int64 g = std::__gcd(u, f);
        gset.insert(g);
    }

    // Mark bad divisors: divisors of any g in gset.
    unordered_set<int64> bad;
    bad.reserve(divisors.size() * 2 + 1);

    for (int64 g : gset) {
        // factor exponents of g w.r.t. f's primes
        vector<int> eg(pf.size(), 0);
        int64 t = g;
        for (int i = 0; i < (int)pf.size(); ++i) {
            int64 p = pf[i].first;
            while (t % p == 0) {
                t /= p;
                ++eg[i];
            }
        }

        function<void(int, int64)> genG = [&](int idx, int64 cur) {
            if (idx == (int)pf.size()) {
                bad.insert(cur);
                return;
            }
            int64 p = pf[idx].first;
            int64 val = 1;
            for (int i = 0; i <= eg[idx]; ++i) {
                genG(idx + 1, cur * val);
                val *= p;
            }
        };
        genG(0, 1);
    }

    long long ans = (long long)divisors.size() - (long long)bad.size();
    cout << ans << '\n';
    return 0;
}