UVa 10179

From Algorithmist
Jump to navigation Jump to search

10179 - Irreducible Basic Fractions[edit]

Summary[edit]

Find the number of irreducible fractions with denominator n.

Explanation[edit]

Given a fraction m/n, for it to be reduced, GCD(m,n) must not be equal to 1. Therefore, the question is reduced to finding the number of positive integers less than n which are relatively prime to n.

What they are asking for is actually to find the value of the Euler's Phi function or totient function for n. So just apply the formula to find the Euler's Phi function and you would get the answer.

Solutions[edit]

Input[edit]

7
12
123456
7654321
0

Output[edit]

6
4
41088
7251444