PROBLEM LINK:
Author: Sobhagya singh dewal
Tester: Sankalp Gupta
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Math
PROBLEM:
Sum of multiplication of each ordered pair of integers from L to R
QUICK EXPLANATION:
(Square of sum of L to R)-(sum of squares of L to R)
EXPLANATION:
We are using the identity:
( a+ b+ c+ d)^2 = a^2 + b^2 + c^2 + d^2 + 2ab +2bc +2ac + 2ad + 2bd + 2cd
2ab +2bc +2ac + 2ad + 2bd + 2cd = ( a+ b+ c+ d)^2 - (a^2 + b^2 + c^2 + d^2)
Extending the above identity for large number of variables will provide the below expression:
sum=(\sum_{i=1}^{r}a_{i})^{2}-\sum_{i=1}^{r}a_{i}^{2} = ((\sum_{i=1}^{l}a_{i})^{2}-\sum_{i=1}^{l}a_{i}^{2})
And we have formulas for sum of first n natural numbers and sum of squares of first n natural numbers .
SOLUTIONS:
Setter’s Solution
#include<bits/stdc++.h>
#define int long long int
int mod=1e9+7;
using namespace std;
int power(int x, int y, int p)
{
int res = 1;
x = x % p;
while (y > 0)
{
if (y & 1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}
int imod(int a, int m)
{
return power(a, m - 2, m);
}
int squre(int n)
{
int ans=n;
ans=((n+1)*ans)%mod;
ans=((2*n+1)*ans)%mod;
ans=(ans*imod(6,mod))%mod;
return ans;
}
int linear(int n)
{
int ans=(n*(n+1))/2;
return ans%mod;
}
int32_t main()
{
int tt;
cin>>tt;
while(tt--)
{
int l,r;
cin>>l>>r;
int xx=(squre(r)-squre(l-1)+10*mod)%mod;
int yy=(linear(r)-linear(l-1)+10*mod)%mod;
int zz=(yy*yy-xx+10*mod)%mod;
cout<<zz<<"\n";
}
}
Tester's Solution
#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define vvl vector<vll>
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vpii vector<pii >
#define vpll vector<pll >
#define ff first
#define ss second
#define PI 3.14159265358979323846
#define fastio ios_base::sync_with_stdio(false) , cin.tie(NULL) ,cout.tie(NULL)
ll power(ll a,ll b){ ll res=1; while(b>0){ if(b&1) res*=a; a*=a; b>>=1;} return res; }
ll power(ll a,ll b,ll m){ ll res=1; while(b>0){ if(b&1) res=(res*a)%m; a=(a*a)%m; b>>=1;} return res;}
bool pp(int a,int b) {return a>b;}
using namespace std;
ll m=1e9+7;
ll mul(ll a,ll b){
return (a*b)%m;
}
ll qube(ll a){
ll res=a;
res = mul(res,a+1);
res = mul(res,2*a+1);
res = mul(power(6,m-2,m),res);
return res;
}
void solve(){
ll l,r;
cin>>l>>r;
assert(r<=1e8&&r>=l&&l>0);
ll sum=0;
ll lint = r*(r+1) - l*(l-1);
lint = lint/2;
lint = lint%m;
ll rint = (qube(r) - qube(l-1) + m)%m;
sum = (mul(lint,lint) - rint + m)%m;
cout<<(sum)<<"\n";
}
int main()
{
fastio;
int t;
cin>>t;
assert(t<=1e5&&t>0);
while(t--){
solve();
}
return 0;
}