Soluție HackerRank pentru Tile Painting: Revisited!, subdomeniul Combinatorics, în C++14. Include cerința formatată, exemple, explicația pașilor și cod…
- Problemă: Tile Painting: Revisited!
- Domeniu: Combinatorics
- Limbaj: C++14
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
Cerință
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 ≤ T ≤ 10
* 1 ≤ N ≤ 10^10
Scoring
* 1 ≤ N ≤ 2000 for 20% of test data.
* 1 ≤ N ≤ 10^5 for 50% of test data.
* 1 ≤ N ≤ 10^10 for 100% of test data.
Cod sursă
#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;
}