Fie șirul Fibonacci dat prin F1 = 1, F2 = 1 și relația de recurență Fk = Fk-1 + Fk-2, k ≥ 3. Se consideră un număr natural N.

Cerința

Să se scrie un program care determină numărul F al fracțiilor diferite ireductibile subunitare, ce se pot forma utilizând primii N termeni ai șirului Fibonacci.

Date de intrare

Fișierul de intrare fibofrac.in conține pe prima linie numărul N.

Date de ieșire

Fișierul de ieșire fibofrac.out va conține pe prima linie numărul F, cu semnificația de mai sus.

Restricții și precizări

• Pentru teste în valoare de 24 puncte, 0 < N < 80
• Pentru teste în valoare de 40 puncte, 0 < N < 1101
• Pentru teste în valoare de 56 puncte, 0 < N < 50001
• Pentru teste în valoare de 100 puncte, 0 < N < 1.000.000
• Două fracții ireductibile a / b și c / d sunt diferite dacă a ≠ c sau b ≠ d.
• 0 ≤ F < 263

Exemplul 1:

fibofrac.in

7

fibofrac.out

14

Explicație

N = 7; Primii 7 termeni ai șirului Fibonacci sunt: 1, 1, 2, 3, 5, 8, 13. Se pot forma 14 fracții diferite ireductibile subunitare: 1/2, 1/3, 1/5, 1/8, 1/13, 2/3, 2/5, 2/13, 3/5, 3/8, 3/13, 5/8, 5/13, 8/13.

Exemplul 2:

fibofrac.in

2019

fibofrac.out

1547722

Exemplul 3:

fibofrac.in

500000

fibofrac.out

94988288219

#include <bits/stdc++.h>
using namespace std;
ifstream cin("fibofrac.in");
ofstream cout("fibofrac.out");
int E[1000001], n;
long long int t;
int main(){
    cin >> n;
    for(int i = 1; i <= n; ++i)
        E[i] = i - 1;
    E[1] = 1;
    for(int i = 2; i <= n; ++i)
        for(int j = 2 * i; j <= n; j = j + i)
            E[j] = E[j] - E[i];
    for(int i = 1; i <= n; ++i)
        if(i <= n / 2)
            t += 2 * E[i];
        else
            t += E[i];
    cout << t - n - 1;
    return 0;
}