HackerRank Number Theory – Divisor Exploration II

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

Cerinta

You are given $q$ queries where each query is in the form of two integers, $m$ and $a$, such that:
$$n = \prod\limits_{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 = \sum\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 \le q \le 50$  
+ $1 \le m \le 10^5$  
+ $0 \le a \le 10^5$

Cod sursa

#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;
}