Soluție HackerRank pentru Laser Beam, subdomeniul Number Theory, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Laser Beam
- Domeniu: Number Theory
- Limbaj: C++14
Challenge: Laser Beam
Subdomeniu: Number Theory (number-theory)
Scor cont: 120.0 / 120
Submission status: Accepted
Submission score: 1.0
Submission ID: 464775683
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/laser-beam/problem
Cerință
You are standing at position (0,0,0). One enemy is positioned at (x,y,z) for every (x,y,z) such that |x| ≤ N, |y| ≤ N, |z| ≤ N and |x| + |y| + |z| > 0.
You have a single laser beam which you can use to shoot enemies. You can aim it in any direction, and all enemies in that direction will be eliminated. You win if the number of enemies you eliminate is at least M and is divisible by D.
How many directions can you aim the laser so that you win? As the answer can get very large, output the answer modulo 1000000007 (= 10^9 + 7).
Input Format
The first line contains a single integer, T, which is the number of test cases.
The next T lines each contain three integers separated by single spaces, N, M and D.
Output Format
For each test case, output a single line containing the number of directions you can aim the laser, modulo 1000000007.
Constraints
1 ≤ T ≤ 3
1 ≤ N ≤ 3· 10^9
1 ≤ M ≤ 1000
1 ≤ D ≤ 1000
Sample Input
2
3 2 1
100 3 2
Sample Output
26
70946
Explanation
For the first test case, here are the 26 directions you can point the laser beam to:
(-1,-1,-1), (-1,-1,0), (-1,-1,1), (-1,0,-1), (-1,0,0), (-1,0,1)
(-1,1,-1), (-1,1,0), (-1,1,1), (0,-1,-1), (0,-1,0), (0,-1,1)
(0,0,-1), (0,0,1), (0,1,-1), (0,1,0), (0,1,1), (1,-1,-1)
(1,-1,0), (1,-1,1), (1,0,-1), (1,0,0), (1,0,1), (1,1,-1)
(1,1,0), (1,1,1)
Cod sursă
#include <bits/stdc++.h>
using namespace std;
#define REPP(I, A, B) for(int I = (A); I < (B); ++I)
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MS0(X) memset((X), 0, sizeof((X)))
typedef long long LL;
const int MOD = 1e9+7;
const int SIZE = 600000;
LL dp3[SIZE],mul[SIZE],record[SIZE];
void pre(){
REPP(i, 1, SIZE){
dp3[i] += (LL)(i + i + 1) * (i + i + 1) * (i + i + 1) - (LL)(i + i - 1) * (i + i - 1) * (i + i - 1);
for(int j = i + i; j < SIZE; j += i){
dp3[j] -= dp3[i];
}
dp3[i] += dp3[i - 1];
dp3[i] %= MOD;
}
}
int main(){
pre();
CASET{
MS0(record);
MS0(mul);
LL N, an = 0;
int M, D;
scanf("%lld%d%d", &N, &M, &D);
LL now = 1;
while(now <= N){
LL v = N / now;
LL nxt = N / v;
if(v >= M){
if(v % D == 0){
if(nxt < SIZE)
an += dp3[nxt];
else
mul[v]++;
if(now - 1 < SIZE)
an -= dp3[now - 1];
else
mul[v + 1]--;
}
}
now = nxt + 1;
}
int ker = 1;
while(N / ker >= SIZE) ker++;
int bb = ker;
for(ker--; ker > 0; ker--){
LL n = N / ker;
LL me = (n + n + 1) % MOD;
record[ker] = (me * me % MOD * me % MOD - 1);
for(now = 2; ker * now < bb; now++)
record[ker] -= record[ker * now];
while(now <= n){
LL v = n / now;
LL nxt = n / v;
if(v < SIZE){
record[ker] -= dp3[v] * (nxt - now + 1);
record[ker] %= MOD;
}
now = nxt + 1;
}
record[ker] %= MOD;
if(record[ker] < 0) record[ker] += MOD;
if(mul[ker]) an += mul[ker] * record[ker];
}
an %= MOD;
if(an < 0) an += MOD;
cout << an << endl;
}
return 0;
}