2478. Farey Sequence

The Farey Sequence F_n for any integer n with n ≥ 2 is the set of irreducible rational numbers a / b with 0 < a < b ≤ n and gcd(a, b) = 1 arranged in increasing order. The first few are

F₂ = {1/2}

F₃ = {1/3, 1/2, 2/3}

F₄ = {1/4, 1/3, 1/2, 2/3, 3/4}

F₅ = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}

You task is to calculate the number of terms in the Farey sequence F_n.

Input. There are several test cases. Each test case has only one line, which contains a positive integer n (2 ≤ n ≤ 10⁶). There are no blank lines between cases. A line with a single 0 terminates the input.

Output. For each test case, you should output one line, which contains N(n) – the number of terms in the Farey sequence F_n. 

Sample Input

2

3

4

5

0

Sample Output

1

3

5

9

РЕШЕНИЕ

рекурсия – последовательность Фарея

Анализ алгоритма

Количество членов N(n) для n ≥ 2 в последовательности Фарея F_n равно

N(n) = ,

где φ(n) – функция Эйлера. Поскольку n ≤ 10⁶, то в ячейках массива f[i] вычислим все частичные суммы . Для избежания Time Limit все значения функции Эйлера φ(k) (2 ≤ k ≤ 10⁶) следует вычислить при помощи решета Эратосфена за O(n loglog n).

Реализация алгоритма

#include <stdio.h>

#include <string.h>

#define MAX 1000010

int i, n;

long long f[MAX];

int fi[MAX];

void FillEuler(void)

{

int i, j;

memset(fi,0,sizeof(fi)); fi[1] = 1;

for(i = 2; i < MAX; i++)

if(!fi[i])

for(j = i; j < MAX; j += i)

{

if(!fi[j]) fi[j] = j;

fi[j] -= fi[j]/i;

}

}

int main(void)

{

FillEuler();

f[1] = 0;

for(i = 2; i < MAX; i++)

f[i] = f[i-1] + fi[i];

while(scanf("%d",&n),n)

printf("%lld\n",f[n]);

return 0;

}