PROBLEM LINK:
Practice
Contest
Author:Srijan Agrawal
Tester:Yash Sharma
Editorialist:Yash Sharma
PROBLEM EXPLANATION:
Find the sum of alternate consecutive d odd numbers from the range L to R inclusive and the number of odd numbers between L and R (both inclusive) is a multiple of d.
DIFFICULTY:
Easy
PREREQUISITES:
None
EXPLANATION:
First thing we need to figure out is the number odd numbers between L and R and starting from first odd number sum of first d odd number can be calculated using summation formula of AP with common difference of 2. Let it be K , so the sum of next d odd numbers will be :
This can be seen as we know that the difference between i^{th} number and (d+i)^{th} odd number is 2*d (take any example). so for all next d numbers the difference will become (d*2*d) i.e 2*d^2.
So the series will become : K, K + 2*d^2, K + 4*d^2, K + 6*d^2, K + 8*d^2 and so on. But we need the sum of alternate d odd numbers so our AP will be become K, K + 4*d^2, K + 8*d^2, K + 12*d^2 and so on.
Clearly this is an AP with common difference 4*d^2 and the sum of this AP with modulo 10^9 + 7 is our answer.
AUTHORS AND TESTERS SOLUTIONS :
Setter's Solution
import sys
#sys.stdin=open('input3.txt','r')
#sys.stdout=open('output3.txt','w')
mod=10**9+7
t=int(input())
for _ in range(t):
d=int(input())
l,r=map(int,input().split())
if(l%2==0):
l+=1
if(r%2==0):
r-=1
first=l+(d-1)
last=r-(d-1)
#print(first,last)
n=(last-first)//(4*d)+1
#print(n)
print((n*(first+last)*d//2)%mod)
Tester's Solution
#include <bits/stdc++.h>
#define ll long long
#define dl double
#define rep(i,n) for(int i = 0; i < n; i++)
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.rbegin(), cont.rend()
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define IN(A, B, C) assert( B <= A && A <= C)
#define unique(a) sort((a).begin(), a.end()), (a).erase(unique((a).begin(),
(a).end()),(a).end())
#define Assert(x) {if(!(x)){cerr<<"Assertion failed at line "<<__LINE__<<": "
<<#x<<" = "<<(x)<<"\n";exit(1);}}
#define MP make_pair
#define PB push_back
#define INF (int)1e9
#define mod 1000000007
using namespace std;
int main()
{
ll i,j,n,m,a,b,t,d,l,r,co;
cin>>t;
while(t--)
{
cin>>d;
cin>>l>>r;
if(l%2 == 0 && r%2 == 0)
{
n = (r-l)/2;
}
else
{
n = (r-l)/2;
n = n+1;
}
co = n/(2*d);
ll temp = n - (co*2*d);
if(temp >= d)
{
co += 1;
}
if(l%2 == 0)
l = l+1;
co--;
ll ans = (sum*(co+1)%mod+ (d*(co*(4*d + (co-1)*
(2*d)%mod))%mod)%mod)%mod;
cout<<ans%mod<<"\n";
}
return 0;
}