### 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.