Question

Dându-se şirul de fracţii 1/N, 2/N, 3/N, ...,N/N, să se afle câte fracţii sunt ireductibile.

Date de intrare
Programul citește de la tastatură numărul N.

Date de ieșire
Programul va afișa pe ecran numărul de fracţii ireductibile.

Restricții și precizări
1 ≤ n ≤ 2.000.000.022

Answer 1

Am atasat solutia. Bafta!

15129cf92de3b036e26863ae84e46ca1.cpp

Answer 2

#include <iostream>
using namespace std;
int n, fm, d, p, i;
unsigned long long nr = 1;
int main()
{
    cin >> n;
    d = 2;
    do
    {
        fm = 0;
        while(n % d == 0)
        {
            fm = fm + 1;
            n = n / d;
        }
        if(fm > 0)
        {
           p = 1;
           for(i = 1; i < fm; i ++)
            p = p * d;
           nr = nr * (d - 1) * p;
        }
        d ++;
        if(n > 1 && d * d > n) nr = nr * (n - 1), n = 1;
    } while(n > 1);
    cout << nr;
    return 0;
}