# PROBLEM LINK:

Practice

Contest : Click here

* Author:* shrivas7

*horsbug98*

**Tester:***shrivas7*

**Editorialist:**# DIFFICULTY:

EASY

# PREREQUISITES:

Modular Arithmetic, AP

# EXPLANATION:

The main objective is to calculate the no. of checkpoints till a distance less than equal to N. Thereafter we can use sum of n terms formula to calculate the total distance that Chef needs to cover in order to complete the race.

For the first check chef has to cover K+K=2Kmiles, similarly for the second checkpoint he needs to cover 2K+2K=4K miles, then 6K, 8K and so on.

Now if we sum all the distance we get, (2K+4K+6K+8K…)

which can be written as 2K(1+2+3+… +x), where x is the total no. of checkpoints. So the total distance covered is

K * x * (x+1), but the race is not yet complete, Chef is at the starting point after removing all the checkpoints now he has to cover more N miles to complete the race. Therefore the total distance to be covered is given by

K * x * (x+1)+N, but the answer may be too long therefore modulo 1000000009 is used.

# SOLUTIONS:

## Setter's Solution

#include<bits/stdc++.h>

#define ll long long int

#define m 1000000007

using namespace std;

int main(){

ll t,n,k;

cin>>t;

while(t–)

{

cin>>n>>k;

ll x = n/k;

ll ans = ((k%m) * (x%m))%m;

ans = (ans * ((x+1)%m))%m;

ans = (ans + (n%m))%m;

cout<<ans<<endl;

}

}

## Tester's Solution

#include “bits/stdc++.h”

using namespace std;

#define ll long long

const ll MOD = (ll)(1e9+7);

ll modmult(ll a, ll b) {

ll res = 0;

a %= MOD;

while(b) {

if(b&1)

res = (res+a)%MOD;

a = (a<<1)%MOD;

b >>= 1;

}

return res;

}

int main() {

ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

int t;

cin >> t;

while(t–) {

ll n, k;

cin >> n >> k;

ll m = n/k;

ll res = modmult(m, (m+1)*k);

res = (res + n)%MOD;

cout << res << ‘\n’;

}

return 0;

}