×

# AUDH-Editorial

Contest

Author: Arnab Das

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.

This question is marked "community wiki".

5★math10
34
accept rate: 0%

19.8k350498541

 0 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 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,678
×631
×301
×27
×1

question asked: 25 Mar '16, 22:37

question was seen: 955 times

last updated: 17 Sep '16, 12:10