You are not logged in. Please login at www.codechef.com to post your questions!

×

AUDH-Editorial

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.

This question is marked "community wiki".

asked 25 Mar '16, 22:37

math10's gravatar image

5★math10
34
accept rate: 0%

edited 29 Mar '16, 16:02

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 17 Sep '16, 12:10

itsnaveen01's gravatar image

3★itsnaveen01
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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