PROBLEM LINK:Author: Arnab Das DIFFICULTY:EASYMEDIUM PREREQUISITES:Sieve, Euler's totient function PROBLEM:Given two number A and B. Number of coprime 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 coprimes 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 precalculate the answers for the range 110^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.
This question is marked "community wiki".
asked 25 Mar '16, 22:37

Hey, Arnab Can You Explain Your Code ? How Did You Initialize The Check Array And What is You Combine Logic For sieve_phi()??? answered 17 Sep '16, 12:10
