PROBLEM LINK:
Author:
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;
}