UVA 10179 Irreducible Basic Fractions Solution

 Solution in C++:

///**********ALLAH IS ALMIGHTY************///

///AH Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh  

Explain: This problem is  explained it is irreducible if gcd(m, n) = 1 .Here given input n(numerator)  and m(denominator) is 1,2,3......n.So,web find how many gcd(m,n) is 1

so,We are using Euler’s Totient function.Euler’s Totient function Φ (n) for an input n is the count of numbers in {1, 2, 3, …, n} that are relatively prime to n, i.e., the numbers whose GCD (Greatest Common Divisor) with n is 1.

#include<bits/stdc++.h>

using namespace std;

int r,i;

int phi (int n)

{

    r=n;

    for(i=2; i*i<=n; i++)

    {

        if(n%i==0)

        {

            while(n%i==0)

                n=n/i;

            r-=r/i;

        }

    }

    if(n>1)

        r-=r/n;

    return r;

}

int main()

{

    int n;

    while((cin>>n)&&n!=0)

    {

        cout<<phi(n)<<endl;

    }

}