SHADOW - EDITORIAL

PROBLEM LINK:

Practice
Contest

Author:

Saurabh Yadav

DIFFICULTY:

EASY

PREREQUISITES:

Math, Implementation

PROBLEM:

Given two numbers A and B and a given range [L, R].Find the sum of numbers divisible by A, the sum of numbers divisible by B and sum of numbers divisible by both A and B(i.e divisible by LCM(A, B) ). Finally, check the given conditions:-

  • If absolute(PS - the sum of numbers divisible by LCM of A and B) is divisible by 2 .
  • If PS( Sum of numbers divisible by A + Sum of numbers divisible by B ) is divisible by 3 or 2 .

EXPLANATION:

An observation can be made that the numbers divisible by a given number X in [L, R] form Arithmetic progression. The formula of the sum of AP can be used to find the sum:-

\frac n 2 \times (2 \times a+(n-1) \times d)

Divisors of A between [L, R] can be found by R /A - (L - 1) / A , similarly Divisors of B between [L, R] can be found by R/B - (L - 1)/B. Divisors of LCM(A,B) can be found by R/LCM(A,B) - (L - 1) /LCM(A,B). First term(a) of each series can be found by finding the smallest number greater than or equal to L which is divisible by given number X (A, B, or LCM(A, B) ).

Sum of numbers divisible by A are:

\frac {(Divisors of A)} 2 \times (2 \times first term + (Divisors of A -1 ) \times A )

Sum of numbers divisible by B are:

\frac {(Divisors of B)} 2 \times (2 \times first term + (Divisors of B -1 ) \times B )

Sum of numbers divisible by LCM(A, B) are:

\frac {(Divisors of LCM(A,B))} 2 \times (2 \times first term + (Divisors of LCM(A,B) -1 ) \times LCM(A,B) )

Note: Suppose L=10 and R=20, it is also possible that L=20 and R=10. In such case swap the values.

Solution:

Authors Solution

#include<bits/stdc++.h>
using namespace std;

long long int findNumlargest(long long int N, long long int K)
{
long long int rem = (N + K) % K;

if (rem == 0) 
    return N; 
else
    return N + K - rem; 

}
long long int FindLCM(long long int a, long long int b)
{
return (a * b) / __gcd(a, b);
}

void rangesum(long long int l, long long int r, long long int a, long long int b)
{

long long int lcm = FindLCM(a, b),ans,sumA,sumB,sumLCM,PS,count=0,check; 

long long int a_divisor = r / a - (l - 1) / a; 
long long int b_divisor = r / b - (l - 1) / b; 
long long int common_divisor = r / lcm - (l - 1) / lcm; 
long long int a1,l1,a2,l2,a3,l3;
a1=findNumlargest(l,a); //Finding the first term of each series i.e a
a2=findNumlargest(l,b);
a3=findNumlargest(l,lcm);
sumA=(a_divisor*(2*a1+(a_divisor-1)*a))/2;
sumB=(b_divisor*(2*a2+(b_divisor-1)*b))/2;
sumLCM=(common_divisor*(2*a3+(common_divisor-1)*lcm))/2;
PS=(sumA+sumB);
check=abs(PS-sumLCM);
if(check%2==0)
	count++;
if(PS%2==0||PS%3==0)
	count++;
if(count==2)
	cout<<"TRUE LOVE"<<endl;
else if(count==1)
	cout<<"LOVE"<<endl;
else cout<<"FAKE LOVE"<<endl;

}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t–){
long long int a,b,l,r;
cin>>a>>b>>l>>r;
if(l<=r)
rangesum(l,r,a,b);
else
rangesum(r,l,a,b);
}

return 0;
}

3 Likes