HackerRank Number Theory – Laser Beam

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

Cerinta

You are standing at position $(0,0,0)$. One enemy is positioned at $(x,y,z)$ for every $(x,y,z)$ such that $|x| \le N$, $|y| \le N$, $|z| \le 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 \le T \le 3$  
$1 \le N \le 3\cdot 10^9$  
$1 \le M \le 1000$  
$1 \le D \le 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 sursa

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