Uva 12995 Solution

Farey Sequence : (Euler totient function)

f(n) = 1+ phi(1) + phi(2) + phi(3) + ............. + phi(n). (1 for 0/1) 

If a/b is a fraction, a and b is co-prime. Its means gcd(a, b) = 1.

Consider two fractions x/y and a/b. we assume that b >= y so 1 <= y <= b-1 (cz for y = 0 and y = b there is no solution) .

 

First consider (ay - bx)  = 1. Here for every 'a' such that g(a, b) = 1 we have exactly one solution.

One more comes from (ay - bx) = -1 . That gives us summation of, 

                                        (2*phi(1) + 2*phi(2) + 2*phi(3) + ................. + 2*phi(n)).

 And from that we have to subtract number of consecutive pairs. Which is 1 smaller than number of fractions. Which is,

 

                                       1 + (phi(1) + phi(2) + phi(3) + .................. + phi(n)).

That means,  non consecutive fraction = (all fraction - consecutive fraction).

All fraction means from we see above for (ay - bx) = 1 and (ay - bx) = -1 we get  2*phi(i) fraction for every i. 

#include<bits/stdc++.h>

#define ll long long int

#define N 1000006

using namespace std;

int p[N+2], phi[N+2];

ll pre[N+2];

void euler_totient()

{

for(int i=1;i<=N;i++)

{

phi[i] = i;

p[i] = 1;

}

phi[0] = phi[1] = p[0] = p[1] = 0;

for(int i=2; i<=N; i++)

{

if(p[i])

{

for(int j=i; j<=N; j+=i)

{

p[j] = 0;

phi[j] = phi[j]/i*(i-1);

}

}

}

}

void presum()

{

pre[0] = pre[1] = 0;

for(int i=2; i<= N; i++)

pre[i] = pre[i-1] + phi[i];

}

int main()

{

euler_totient();

presum();

int n;

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

{

cout << pre[n] << "\n";

}

    return 0;

}