Challenge: Divisor Exploration 3
Subdomeniu: Number Theory (number-theory)
Scor cont: 55.0 / 55
Submission status: Accepted
Submission score: 1.0
Submission ID: 464753844
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/divisor-exploration-3/problem
Cerinta
You are given $q$ queries where each query is in the form of three integers, $m$, $a$ and $d$, such that:
$$n = \prod\limits_{i = 1}^{m} p_i^{a+i} \text{, where } p_i \text{ is the } i^{th} \text{ prime.}$$
Using this value of $n$ along with the given $d$, create a tree $T$ as follows :-
+ The value $n$ is the root of the tree.
+ A node is expanded such that all it's divisors are it's children.
+ Continue expanding till the tree has depth $d$.
For example, if $n = 6$ and $d = 2$, then the tree will look like the following:
Once the tree is built, we create another tree $U$ as follows :-
+ Every leaf node $x \in T$, is transformed to $\phi(x)$. Here $\phi()$ is the totient function.
+ Every non-leaf node is equal to the sum of the values of it's children.
From our previous example tree, after constructing a new tree, we get the following tree.
Print the value at the root of tree $U$ after taking modulo with $(10^9+7)$.Input Format
The first line of the input contains a single integer $q$ ( $q \leq 50$ ).
Following $q$ lines contain three integers given by $m$, $a$ and $d$.Output Format
For each case, print the value at the root of tree $U$ modulo $(10^9+7)$.Constraints
**For $30\%$ points:**
+ $1 \leq m \leq 100$
+ $0 \leq a \leq 100$
+ $1 \leq d \leq 100$
**For Full Points:**
+ $1 \leq m \leq 1000$
+ $0 \leq a \leq 1000$
+ $1 \leq d \leq 1000$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<tuple<int,int,int>> qs(q);
int max_m = 0, max_a = 0, max_d = 0;
for (int i = 0; i < q; ++i) {
int m, a, d;
cin >> m >> a >> d;
qs[i] = {m, a, d};
max_m = max(max_m, m);
max_a = max(max_a, a);
max_d = max(max_d, d);
}
// First max_m primes.
int LIM = 100000;
while (true) {
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);
}
if ((int)primes.size() == max_m) {
// Prepare factorials for combinations up to (max_e + max_d).
int max_e = max_a + max_m;
int max_n = max_e + max_d + 5;
vector<long long> fact(max_n + 1, 1), inv_fact(max_n + 1, 1);
for (int i = 1; i <= max_n; ++i) fact[i] = fact[i - 1] * i % MOD;
inv_fact[max_n] = mod_pow(fact[max_n], MOD - 2);
for (int i = max_n; i >= 1; --i) inv_fact[i - 1] = inv_fact[i] * i % MOD;
auto nCr = [&](int n, int r) -> long long {
if (r < 0 || r > n) return 0;
return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD;
};
for (auto [m, a, d] : qs) {
long long ans = 1;
for (int i = 1; i <= m; ++i) {
long long p = primes[i - 1];
int e = a + i;
long long g;
if (d == 1) {
g = mod_pow(p, e);
} else {
// G_d(e) = sum_{t=0..e} C(e-t + d-2, d-2) * p^t
long long pw = 1;
g = 0;
for (int t = 0; t <= e; ++t) {
int nn = (e - t) + (d - 2);
long long c = nCr(nn, d - 2);
g = (g + c * pw) % MOD;
pw = (pw * p) % MOD;
}
}
ans = (ans * g) % MOD;
}
cout << ans << '\n';
}
return 0;
}
LIM *= 2;
}
}
HackerRank Number Theory – Divisor Exploration 3