ENOC4 -Editorial

PROBLEM LINK:

Practice
Contest : Click here

Author: shrivas7
Tester: horsbug98
Editorialist: shrivas7

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;
}