Challenge: GCD mocktail
Subdomeniu: Number Theory (number-theory)
Scor cont: 150.0 / 150
Submission status: Accepted
Submission score: 1.0
Submission ID: 464775788
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/gcd-mocktail/problem
Cerinta
The Rebel Alliance and the Galactic Empire are engaged in an epic battle in the skies above Endor. The grand setup has d-dimensional board with each dimension of length 'N', (i.e) N x N... (d times). Each cell (i<sub>1</sub>, i<sub>2</sub>, ...i<sub>d</sub>) has the gcd (i<sub>1</sub>, i<sub>2</sub>, ...i<sub>d</sub>) written on it.
Now, the game begins. A random integer <i>L</i> is chosen and the first person to sum up the L<sup>th</sup> power of each number modulo 30000001 wins the game.
Rebel Alliance needs some help and pings you. If they win, you get a million dollars for it. Can you help?
**Input Format**
There are several test cases. The first line contains the number of test cases T. Then T test cases follow. Each test case is given in the following format.<br/>
N and d are given in the first Line.<br/>
Q is given in the second line.<br/>
Each of the next Q lines contain an integer L.
**Constraints**
0<=T<=10
1<=N<=10<sup>7</sup>
1<=d<=1000
0<=L<=100
0<=Q<=50
**Output Format**
For each test case, output Q lines, indicating the answer.
**Sample Input**
3
3 2
4
0
1
2
3
5 1
3
0
1
2
6 3
2
2
3
**Sample Output**
9
12
20
42
5
15
55
421
975
**Explanation**
Test case1:
the board is as follows:
1(gcd 1,1) 1(gcd 1,2) 1(gcd 1,3)
1(gcd 2,1) 2(gcd 2,2) 1(gcd 2,3)
1(gcd 3,1) 1(gcd 3,2) 3(gcd 3,3)
Therefore,
sum of 0th power is 1^0+1^0+1^0 + 1^0+2^0+1^0 + 1^0+1^0+3^0 = 9
sum of 1st power is 1^1+1^1+1^1 + 1^1+2^1+1^1 + 1^1+1^1+3^1 = 12
so on ...
Test case2:
the board is as follows:
1(gcd 1) 2(gcd 2) 3(gcd 3) 4(gcd 4) 5(gcd 5)
Therefore,
sum of 0th power is 1^0+2^0+3^0+4^0+5^0 = 5
sum of 1st power is 1^1+2^1+3^1+4^1+5^1 = 15
so on ...Cod sursa
#include <bits/stdc++.h>
#define ll long long
#define mod 30000001
#define L 110
#define N 10000010
ll ipow(ll b, ll e){
if(e == 0) return 1;
if(e == 1) return b;
if(e & 1) return ipow(b, e - 1) * b % mod;
return ipow(b * b % mod, e >> 1);
}
ll inv[L + 2];
ll A[L + 1];
ll B[L + 1];
ll C[L + 1][L + 1];
ll P[L + 1];
ll G[N + 1];
int main(){
inv[0] = inv[1] = 1;
for(int i = 2; i <= L + 1; i++){
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
for(int i = 0; i <= L; i++){
for(int m = 0; m <= i; m++){
A[m] = inv[m + 1];
for(int j = m; j; j--){
A[j - 1] = j * (A[j - 1] - A[j]) % mod;
}
}
B[i] = A[0];
}
G[0] = 0;
for(int n = 0; n <= L; n++){
for(int r = 0; r <= L; r++){
if(r > n){
C[n][r] = 0;
} else if(r == 0 or r == n){
C[n][r] = 1;
} else{
C[n][r] = (C[n - 1][r - 1] + C[n - 1][r]) % mod;
}
}
}
int z;
scanf("%d", &z);
while(z--){
int n, d;
scanf("%d%d", &n, &d);
int c = int(fmin(n, pow(n, 2./3) * pow(log(n + 1), 1./3) * 2)) + 1;
for(int i = 1; i < c; i++){
G[i] = ipow(i, d) - ipow(i - 1, d);
}
for(int i = 1; i < c; i++){
G[i] %= mod;
for(int j = i << 1; j < c; j += i){
G[j] -= G[i];
}
G[i] += G[i - 1];
G[i] %= mod;
}
for(int k = n / c; k; k--){
int i = n / k;
int u = int(sqrt(i)) + 1;
ll t = ipow(i, d);
for(int g = i / u; g > 1; g--){
t -= G[i / g];
}
t %= mod;
for(int v = 1; v < u; v++){
t -= (i / v) * (G[v] - G[v - 1]);
t %= mod;
}
t += (i / u) * G[u - 1];
G[i] = t % mod;
}
int q;
scanf("%d", &q);
while(q--){
int l;
scanf("%d", &l);
ll t;
if(l == 0){
t = ipow(n, d);
} else{
for(int k = 0; k <= l; k++){
P[k] = C[l + 1][k] * B[k] % mod;
}
ll res;
#define set_F(_w) do {\
ll w = (_w);\
res = 0;\
for(int k = 0; k <= l; k++){\
res += P[k];\
res *= w;\
res %= mod;\
}\
} while(0)
int u = int(sqrt(n / l)) + 1;
t = 0;
for(int v = 1; v < u; v++){
set_F(n / v);
t += res * (G[v] - G[v - 1]);
t %= mod;
}
set_F(n / u);
t -= res * G[u - 1];
t %= mod;
t *= inv[l + 1];
t %= mod;
for(int g = n / u; g; g--){
t += ipow(g, l) * G[n / g];
t %= mod;
}
}
if(t < 0) t += mod;
printf("%lld\n", t);
}
}
}
HackerRank Number Theory – GCD mocktail