SCC0106 - Editorial

SCC0106 - Editorial

PROBLEM LINK:

Contest

Practice

PROBLEM NAME: Who is my friend.

Author: Learners Club

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Prime Numbers, Euler Totient function

PROBLEM:

In short, We are required to find the count of all the positive numbers less than N which are coprime to the given number N.

EXPLANATION:

This is a direct application of Euler Totient Function.
Look up wikipedia to understand it and give it a try on the practice section.

Important point to know is that For N = 1 the Answer is 1, Find out why… ?

RELATED PROBLEMS:

ETF