HackerRank Algebra – The Simplest Sum

Challenge: The Simplest Sum

Subdomeniu: Algebra (algebra)

Scor cont: 50.0 / 50

Submission status: Accepted

Submission score: 1.0

Submission ID: 464738680

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/the-simplest-sum/problem

Cerinta

You are just learning to code and are finished with loops and functions. Now, you are given the following pseudocode:

```cpp
/*
 * The function has two integer parameters: k and n
 * The function returns the value of sum
 */
function f(k, n) {
    sum = 0;

    for (i = 1; i ≤ n; i += 1) {
        sum += i;
        i *= k;
    }

    return sum;
}
```

For three given integers $k$, $a$, and $b$, find the value of $S \bmod \left(10^{9} + 7\right)$, where $S$ is defined as:
$$S = \sum_{n\ =\ a}^{b} f(k,\ n)$$

Input Format

The first line of the input is an integer $Q$, the total number of queries. Each of the next $Q$ lines contains three space separated integers $k$, $a$, and $b$.

Output Format

For each query, print the value of $S \bmod \left(10^{9} + 7\right)$ on a new line.

Constraints

- $1 \le Q \le 10^{5}$
- $2 \le k \le 10^{5}$
- $1 \le a \le b \le 10^{18}$

Cod sursa

#include <iostream>
#include <vector>

using namespace std;

void solve() 
{    
    long long k, left, right; 
    cin >> k >> left >> right;
    
    vector <long long> terms; 
    terms.push_back(1); 
    while(terms.back() <= (right - 1)/k)
    {
        long long next = terms.back()*k + 1; 
        terms.push_back(next);
        //cout << "Last term " << terms.back() << "\n";
    }
    
    const int MOD = 1e9 + 7;
    long long answer = 0;
    for(long long term : terms)
    {
        long long contribution = right - max(left - 1, term - 1);
        contribution %= MOD;
        
        answer += (term*contribution)%MOD;
        answer %= MOD;
    }
    
    cout << answer << "\n";
}

int main()
{
    int no_of_queries; 
    cin >> no_of_queries; 
    
    while(no_of_queries--)
        solve();
    
    return 0;
}