PROBLEM LINKS:
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).
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