Soluție HackerRank pentru Number of M-Coprime Arrays, subdomeniul Number Theory, în C++14. Include cerința formatată, exemple, explicația pașilor și cod…

  • Problemă: Number of M-Coprime Arrays
  • Domeniu: Number Theory
  • Limbaj: C++14

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

Cerință

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 ≤ q ≤ 100
- 1 ≤ n, m ≤ 10^18

Cod sursă

#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