Divisor Exploration II HackerRank: soluție Number Theory C++14

Soluție HackerRank pentru Divisor Exploration II, subdomeniul Number Theory, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.

Problemă: Divisor Exploration II
Domeniu: Number Theory
Limbaj: C++14

Challenge: Divisor Exploration II

Subdomeniu: Number Theory (number-theory)

Scor cont: 50.0 / 50

Submission status: Accepted

Submission score: 1.0

Submission ID: 464753750

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/divisor-exploration-2/problem

Cerință

You are given q queries where each query is in the form of two integers, m and a, such that:
n = prodlimits_i = 1^m p_i^a+i text{, where } p_i text{ is the } i-th text{ prime.}

For each query, find the following value:

result = ∑limits_x|n sigma_1(x)

where x|n denotes that each x is a [divisor](https://en.wikipedia.org/wiki/Divisor) of n and sigma_1(x) is the *sum of the divisors* of x. Then print the value of result bmod (10^9 + 7) on a new line.

Input Format

The first line contains an integer, q, denoting the number of queries.
Each line i of the q subsequent lines contains two space-separated integers describing the respective values of m_i and a_i for query i.

Output Format

For each query, print a single integer denoting the value of result bmod (10^9 + 7) on a new line.

Constraints

+ 1 ≤ q ≤ 50
+ 1 ≤ m ≤ 10^5
+ 0 ≤ a ≤ 10^5

Cod sursă

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

static const long long MOD = 1000000007LL;

long long mod_pow(long long a, long long e) {
    long long r = 1 % MOD;
    a %= MOD;
    while (e > 0) {
        if (e & 1) r = (r * a) % MOD;
        a = (a * a) % MOD;
        e >>= 1;
    }
    return r;
}

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

    int q;
    if (!(cin >> q)) return 0;
    vector<pair<int,int>> queries(q);
    int max_m = 0;
    for (int i = 0; i < q; ++i) {
        int m, a;
        cin >> m >> a;
        queries[i] = {m, a};
        max_m = max(max_m, m);
    }

    int LIM = 1300000;
    vector<bool> is_prime(LIM + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; 1LL * i * i <= LIM; ++i) {
        if (!is_prime[i]) continue;
        for (int j = i * i; j <= LIM; j += i) is_prime[j] = false;
    }

    vector<int> primes;
    primes.reserve(max_m);
    for (int i = 2; i <= LIM && (int)primes.size() < max_m; ++i) {
        if (is_prime[i]) primes.push_back(i);
    }

    vector<long long> inv_sq(max_m);
    for (int i = 0; i < max_m; ++i) {
        long long x = (primes[i] - 1LL) % MOD;
        long long inv = mod_pow(x, MOD - 2);
        inv_sq[i] = (inv * inv) % MOD;
    }

    for (auto [m, a] : queries) {
        long long ans = 1;
        for (int i = 0; i < m; ++i) {
            long long p = primes[i] % MOD;
            long long e = (long long)a + (i + 1);
            long long pw = mod_pow(p, e + 1);

            long long num = (p * ((pw - 1 + MOD) % MOD)) % MOD;
            long long sub = ((e + 1) % MOD) * ((p - 1 + MOD) % MOD) % MOD;
            num = (num - sub + MOD) % MOD;
            long long g = num * inv_sq[i] % MOD;

            ans = ans * g % MOD;
        }
        cout << ans << '\n';
    }
    return 0;
}

HackerRank Number Theory – Divisor Exploration II