HackerRank Combinatorics – Tile Painting: Revisited!

Challenge: Tile Painting: Revisited!

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 70.0 / 70

Submission status: Accepted

Submission score: 1.0

Submission ID: 464757996

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/tile-painting-revisited/problem

Cerinta

Nikita has a row of $N$ white tiles indexed from $1$ to $N$. This time, she's painting them green! 

Find the number of ways Nikita can paint certain tiles in green so that the indices of the green tiles form an [Arithmetic Progression](https://en.wikipedia.org/wiki/Arithmetic_progression). As this value can be quite large, your answer must be modulo $(10^9 + 7)$.

**Note:** Nikita must paint *at least* $1$ tile.

Input Format

The first line contains a single integer, $T$, denoting the number of test cases.	
Each test case consists of a single line containing an integer, $N$, denoting the length of row of tiles.

Output Format

On a new line for each test case, print the number of ways Nikita can paint her white tiles green so that the indices of the green tiles form an [Arithmetic Progression](https://en.wikipedia.org/wiki/Arithmetic_progression). Because this number can be quite large, your answer must be modulo $(10^9+7)$.

Constraints

* $1 \le T \le 10$
* $1 \le N \le 10^{10}$

**Scoring**

* $1 \le N \le 2000$ for $20\%$ of test data.
* $1 \le N \le 10^5$ for $50\%$ of test data.
* $1 \le N \le 10^{10}$ for $100\%$ of test data.

Cod sursa

#include <bits/stdc++.h>
using namespace std;

using i128 = __int128_t;
static const long long MOD = 1000000007LL;

static inline long long modNorm(long long x) {
    x %= MOD;
    if (x < 0) x += MOD;
    return x;
}

static inline long long sumRangeMod(long long l, long long r) {
    // (l + ... + r) mod MOD
    i128 cnt = (i128)(r - l + 1);
    i128 s = (i128)(l + r) * cnt / 2;
    return (long long)(s % MOD);
}

long long solveOne(long long N) {
    if (N == 1) return 1;

    long long M = N - 1;

    long long C = 0; // sum floor(M/a)
    long long T = 0; // sum a * q(q+1)/2

    for (long long l = 1; l <= M;) {
        long long q = M / l;
        long long r = M / q;

        long long cntMod = (r - l + 1) % MOD;
        C = (C + (i128)(q % MOD) * cntMod) % MOD;

        long long sumA = sumRangeMod(l, r);
        long long triQ = (i128)q * (q + 1) / 2 % MOD;
        T = (T + (i128)sumA * triQ) % MOD;

        l = r + 1;
    }

    long long S = modNorm((i128)((M + 1) % MOD) * C % MOD - T); // S = sum_{t=1..M} D(t)
    long long ans = modNorm((N % MOD) + S);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        long long N;
        cin >> N;
        cout << solveOne(N) << '\n';
    }

    return 0;
}