Author: Arnab Das
Sieve, Euler’s totient function
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”.
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 solution can be found here.