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

×

# DRAWAR - Editorial

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). 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 2★mightysg
41
accept rate: 0% 19.8k350498541

 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

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:

×639
×46
×43
×1
×1

question asked: 11 Oct '16, 12:27

question was seen: 600 times

last updated: 02 Jan '17, 18:41