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

×

DRAWAR - Editorial

PROBLEM LINKS:

Practice

Setter : Siddhant Bharti

Tester : Shubham Grover

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Number Theory,Euler's Totient Function

EXPLANATION:

You need to find number of unordered pairs (x,y) whose gcd (greatest common devisor) is 1. So, for each natural number x , if we find number of natural numbers less than x that are co-prime to it and sum these values, we will get the answer.(This value is given by Euler totient function).

alt text

Instead of factorizing each natural number separately for calculating Euler totient function , we can use sieve to calculate them . Let Phi[N] be an array which will store the values of totient function for each x from 1 to N. Initialize it with Phi[x]=x . In sieve while marking multiples of a prime ‘i’ ,divide Phi[j] with i and then multiply it with (i-1). See the code for better understanding :

SETTER'S SOLUTION:

Can be found here

asked 11 Oct '16, 12:27

mightysg's gravatar image

2★mightysg
41
accept rate: 0%

edited 02 Jan '17, 18:41

admin's gravatar image

0★admin ♦♦
19.8k350498541

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:

×639
×46
×43
×1
×1

question asked: 11 Oct '16, 12:27

question was seen: 600 times

last updated: 02 Jan '17, 18:41