×

# 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

2★mightysg
41
accept rate: 0%

19.8k350498541

 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:

×639
×46
×43
×1
×1

question asked: 11 Oct '16, 12:27

question was seen: 600 times

last updated: 02 Jan '17, 18:41