PROBLEM LINK:
Author: Arnab Das
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Sieve, Euler’s totient function
PROBLEM:
Given two number A and B. Number of co-prime 1 to A with A is x and 1 to B with B is y.
if x >= y then “Swapnil lost it” otherwise “Shibli took it”.
QUICK EXPLANATION:
We need to find the number of co-primes of both A and B. This can be done easily by Euler’s totient function. But as the time limit is strict and limit is 10^6 for both and test cases are 10^5, the operation should be faster. Applying sieve on Euler’s totient function helps to pre-calculate the answers for the range 1-10^6. And then it’s just a matter of taking inputs and calculate desired result from the stored ones.
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.