PROBLEM LINKS:Setter : Siddhant BhartiTester : Shubham GroverDIFFICULTY:EasyMedium 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 coprime 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 (i1). See the code for better understanding : SETTER'S SOLUTION:Can be found here asked 11 Oct '16, 12:27
