Soluție HackerRank pentru Divisor Exploration 3, subdomeniul Number Theory, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Divisor Exploration 3
- Domeniu: Number Theory
- Limbaj: C++14
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
Cerință
You are given q queries where each query is in the form of three integers, m, a and d, such that:
n = prodlimits_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 ≤ 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 ≤ m ≤ 100
+ 0 ≤ a ≤ 100
+ 1 ≤ d ≤ 100
For Full Points:
+ 1 ≤ m ≤ 1000
+ 0 ≤ a ≤ 1000
+ 1 ≤ d ≤ 1000
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<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;
}
}