Soluție HackerRank pentru The Simplest Sum, subdomeniul Algebra, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: The Simplest Sum
- Domeniu: Algebra
- Limbaj: C++14
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
Cerință
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 ≤ft(10^9 + 7right), where S is defined as:
S = ∑_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 ≤ft(10^9 + 7right) on a new line.
Constraints
- 1 ≤ Q ≤ 10^5
- 2 ≤ k ≤ 10^5
- 1 ≤ a ≤ b ≤ 10^18
Cod sursă
#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;
}