AUDH-Editorial

audh
aust2016
editorial
number-theory
sieve

#1

PROBLEM LINK:

Contest

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.


#2

Hey, Arnab
Can You Explain Your Code ?
How Did You Initialize The Check Array And What is You Combine Logic For sieve_phi()???