HackerRank Number Theory – Number of M-Coprime Arrays – ASOCIATIA „INVESTESTE PENTRU VIITORUL TAU” BUZAU

Challenge: Number of M-Coprime Arrays

Subdomeniu: Number Theory (number-theory)

Scor cont: 70.0 / 70

Submission status: Accepted

Submission score: 1.0

Submission ID: 464757847

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/number-of-m-coprime-arrays/problem

Cerinta

An array of integers is called $m$-coprime if the following conditions are both satisfied:

- All the integers in the array are positive divisors of $m$.
- Each pair of adjacent elements in the array is [coprime](https://en.wikipedia.org/wiki/Coprime_integers) (i.e., element $i$ is always coprime with element $i + 1$).

Two arrays, $A$ and $B$, of size $n$ are *different* if and only if there exists an index $i$ such that $A[i] \ne B[i]$.

You are given $q$ queries where each query consists of integers $n$ and $m$. For each query, find the number of $m$-coprime arrays of size $n$, modulo $10^9 + 7$, and print it on a new line.

Input Format

The first line contains an integer, $q$, denoting the number of queries.    
Each of the $q$ subsequent lines contains two space-separated integers describing the respective values of $n$ (the size of the array) and $m$.

Output Format

For each query, print the number of $m$-coprime arrays of size $n$ modulo $10^9 + 7$ on a new line.

Constraints

- $1 \le q \le 100 $
- $1 \le n, m \le 10^{18}$

Cod sursa

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

using u64 = unsigned long long;
using u128 = __uint128_t;

static const long long MOD = 1000000007LL;

static inline u64 mod_mul_u64(u64 a, u64 b, u64 mod) {
    return (u128)a * b % mod;
}

static inline u64 mod_pow_u64(u64 a, u64 e, u64 mod) {
    u64 r = 1 % mod;
    a %= mod;
    while (e > 0) {
        if (e & 1) r = mod_mul_u64(r, a, mod);
        a = mod_mul_u64(a, a, mod);
        e >>= 1;
    }
    return r;
}

bool isPrime64(u64 n) {
    if (n < 2) return false;
    for (u64 p : {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL, 19ULL, 23ULL, 29ULL, 31ULL, 37ULL}) {
        if (n % p == 0) return n == p;
    }

    u64 d = n - 1, s = 0;
    while ((d & 1) == 0) {
        d >>= 1;
        ++s;
    }

    // Deterministic MR bases for 64-bit.
    for (u64 a : {2ULL, 325ULL, 9375ULL, 28178ULL, 450775ULL, 9780504ULL, 1795265022ULL}) {
        if (a % n == 0) continue;
        u64 x = mod_pow_u64(a % n, d, n);
        if (x == 1 || x == n - 1) continue;
        bool comp = true;
        for (u64 r = 1; r < s; ++r) {
            x = mod_mul_u64(x, x, n);
            if (x == n - 1) {
                comp = false;
                break;
            }
        }
        if (comp) return false;
    }
    return true;
}

u64 pollardRho(u64 n) {
    if ((n & 1ULL) == 0ULL) return 2;
    static std::mt19937_64 rng((u64)chrono::high_resolution_clock::now().time_since_epoch().count());

    while (true) {
        u64 c = uniform_int_distribution<u64>(1, n - 1)(rng);
        u64 x = uniform_int_distribution<u64>(0, n - 1)(rng);
        u64 y = x;
        u64 d = 1;

        auto f = [&](u64 v) {
            return (mod_mul_u64(v, v, n) + c) % n;
        };

        while (d == 1) {
            x = f(x);
            y = f(f(y));
            u64 diff = x > y ? x - y : y - x;
            d = __gcd(diff, n);
        }
        if (d != n) return d;
    }
}

void factorRec(u64 n, map<u64, int> &mp) {
    if (n == 1) return;
    if (isPrime64(n)) {
        mp[n]++;
        return;
    }
    u64 d = pollardRho(n);
    factorRec(d, mp);
    factorRec(n / d, mp);
}

struct Mat2 {
    long long a00, a01, a10, a11;
};

Mat2 mulMat(const Mat2 &A, const Mat2 &B) {
    Mat2 C;
    C.a00 = ((u128)A.a00 * B.a00 + (u128)A.a01 * B.a10) % MOD;
    C.a01 = ((u128)A.a00 * B.a01 + (u128)A.a01 * B.a11) % MOD;
    C.a10 = ((u128)A.a10 * B.a00 + (u128)A.a11 * B.a10) % MOD;
    C.a11 = ((u128)A.a10 * B.a01 + (u128)A.a11 * B.a11) % MOD;
    return C;
}

Mat2 powMat(Mat2 base, unsigned long long exp) {
    Mat2 res{1, 0, 0, 1};
    while (exp > 0) {
        if (exp & 1ULL) res = mulMat(res, base);
        base = mulMat(base, base);
        exp >>= 1ULL;
    }
    return res;
}

long long waysForPrime(unsigned long long n, long long e) {
    // F(0)=1, F(1)=1+e, F(n)=F(n-1)+e*F(n-2)
    if (n == 0) return 1;
    if (n == 1) return (1 + e) % MOD;

    Mat2 M{1, e % MOD, 1, 0};
    Mat2 P = powMat(M, n - 1);

    long long F1 = (1 + e) % MOD;
    long long F0 = 1;
    long long Fn = ((u128)P.a00 * F1 + (u128)P.a01 * F0) % MOD;
    return Fn;
}

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

    int q;
    cin >> q;
    while (q--) {
        unsigned long long n, m;
        cin >> n >> m;

        if (m == 1ULL) {
            cout << 1 << '\n';
            continue;
        }

        map<u64, int> fac;
        factorRec(m, fac);

        long long ans = 1;
        for (auto &kv : fac) {
            int e = kv.second;
            long long w = waysForPrime(n, e);
            ans = (u128)ans * w % MOD;
        }

        cout << ans << '\n';
    }

    return 0;
}

HackerRank Number Theory – Number of M-Coprime Arrays