UVa 10179

From Algorithmist

Contents 1 10179 - Irreducible Basic Fractions 2 Summary 3 Explanation 4 Input 5 Output

[edit] 10179 - Irreducible Basic Fractions

• http://acm.uva.es/p/v101/10179.html

[edit] Summary

Find the number of irreducible fractions with denominator n.

[edit] Explanation

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.

[edit] Input

7
12
123456
7654321
0

[edit] Output

6
4
41088
7251444