Найти наибольший общий делитель двух чисел Фибоначчи

@Melvil · Регистрация: 20.05.2015

Студворк — интернет-сервис помощи студентам

Добрый вечер, решаю задачу, ошибка на шестом тесте. Условии задачи:

Кликните здесь для просмотра всего текста

Последовательностью Фибоначчи называется последовательность чисел F0 = 0, F1 = 1, … , Fk = Fk-1 + Fk-2 (k > 1).

Требуется найти наибольший общий делитель двух чисел Фибоначчи.

Входные данные

Во входном файле INPUT.TXT записаны два целых числа i и j (1 ≤ i, j ≤ 10 в 6-й степени).

Выходные данные

В выходной файл OUTPUT.TXT выведите остаток от деления НОД чисел Fi и Fj на 10 в 9-й степени.

Шестой тест:

893854 102938

Мой код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>
using namespace std;
 
 
int fib(_int64 n)
{
    if (n <= 2)
    {
        return 1;
    }
    vector<int>dp(n + 1);
    dp[1] = 1; dp[2] = 1;
    for (int i = 3; i <= n; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
int GCD(_int64 a, _int64 b)
{
    while (a != b)
    {
        if (a > b)
           a = a - b;
        else
            b = b - a;
    }
    return a;
}
 
int main()
{
    _int64 a, b;
    cin >> a >> b;
    if (a == 0 && b == 0)
        cout << 0 << endl;
    if (a == 0)
    {
        cout << fib(b) << endl;
        return 0;
    }
    if (b == 0)
    {
        cout << fib(a) << endl;
        return 0;
    }
    a = fib(a);
    b = fib(b);
    _int64 Result = (GCD(a, b));
    cout << Result % 1000000000 << endl;
    return 0;
}

Заранее спасибо!

@Melvil · 15.08.2015, 10:37 **[ТС]**

Сообщение от zer0mail

Это же надо так испоганить эффективный алгоритм нахождения НОДа

Хорошо, давайте возьмем два одинаковых числа, одно из них станет равным нулю и произойдет деление на ноль. В данном же случае этого нет.

@Kerry_Jr · 15.08.2015, 10:49

Melvil, попробуйте так, вроде без деления на ноль

C++
1
2
3
4
5
6
7
8
9
long Nod(long a, long b)
{
    while (a && b)
        if (a >= b)
           a %= b;
        else
           b %= a;
    return a | b;
}

zer0mail · 15.08.2015, 11:19

Сообщение от Melvil

Хорошо, давайте возьмем два одинаковых числа, одно из них станет равным нулю и произойдет деление на ноль. В данном же случае этого нет.

Ну конечно - лучше цикл прогнать 10ⁿ раз, чем 1 раз проверить на 0.

@Mr.X · 15.08.2015, 11:28

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <algorithm>
#include <iostream>
/////////////////////////////////////////////////////////////////////////////////////////
int     gcd
    (
        int     a,
        int     b
    )
{
    return  !b
                ?   a
 
                :   gcd (
                            b,
                            a % b
                        );
}
/////////////////////////////////////////////////////////////////////////////////////////
int     fibb_with_ind_modulo
    (
        int     n,
        int     mod
    )
{
    int     res_1   =   0;
    int     res_2   =   1;
 
    for( int  i = 0; i < n; ++i )
    {
        std::swap
            (
                res_1,
                res_2
            );
 
        res_2   +=  res_1;
        res_2   %=  mod;
    }//for
 
    return  res_1;
}
/////////////////////////////////////////////////////////////////////////////////////////
int     gcd_fib_pair_with_indexes_modulo
    (
        int     i,
        int     j,
        int     mod
    )
{
    int     k   =   gcd (
                            i,
                            j
                        );
 
    return  fibb_with_ind_modulo
                (
                    k,
                    mod
                );
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    int     i   =   0;
    std::cin    >>  i;
 
    int     j   =   0;
    std::cin    >>  j;
 
    std::cout   <<  gcd_fib_pair_with_indexes_modulo
                        (
                            i,
                            j,
                            1000000000
                        );
}

@Melvil · 15.08.2015, 12:34 **[ТС]**

Mr.X, Ааа, как? Как Accepted?

Добавлено через 10 минут
Я не очень понимаю значение данного кода:

C++
1
2
3
4
5
6
7
for (int i = 0; i < n; ++i)
    {
        swap(res_1, res_2);
 
        res_2 += res_1;
        res_2 %= mod;
    }

В данной программе:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <algorithm>
#include <iostream>
using namespace std;
/////////////////////////////////////////////////////////////////////////////////////////
int gcd (int a, int b)
{
    return  !b ? a : gcd(b,a % b);
}
/////////////////////////////////////////////////////////////////////////////////////////
int fibb_with_ind_modulo(int n, int mod)
{
    int  res_1 = 0;
    int  res_2 = 1;
 
    for (int i = 0; i < n; ++i)
    {
        swap(res_1, res_2);
 
        res_2 += res_1;
        res_2 %= mod;
    }
    return  res_1;
}
/////////////////////////////////////////////////////////////////////////////////////////
int gcd_fib_pair_with_indexes_modulo (int i, int j, int mod)
{
    int k = gcd(i,j);
    return  fibb_with_ind_modulo(k, mod);
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    int i = 0;
    cin >> i;
    int j = 0;
    cin >> j;
    cout << gcd_fib_pair_with_indexes_modulo(i,j,1000000000);
}

И чем она вообще отличается от тех, что были ранее, почему проходит все тесты?

@Mr.X · 15.08.2015, 12:47

Сообщение от Melvil

Я не очень понимаю значение данного кода

Ну, чтобы последовательно вычислять числа Фибоначчи нам достаточно помнить последние два. Находим сумму, меньшее отбрасываем. А здесь еще находим не сами числа а по заданному модулю.

Сообщение от Melvil

И чем она вообще отличается от тех, что были ранее, почему проходит все тесты?

Использует свойство

Сообщение от Dani

GCD(Fn, Fm) = FGCD(n, m)

@Melvil · 15.08.2015, 12:52 **[ТС]**

Сообщение от Mr.X

А здесь еще находим не сами числа а по заданному модулю.

Хоть убейте, не вижу, где здесь используется модуль.
А свойство использовалось и в прошлых вариантах или я чего-то не понимаю?:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
 
int fibonacci(int n)
{
    int count = 0;
    int fib = 0, fib1 = 1, fib2 = 1;
    while (true)
    {
        ++count;
        if (count == n) break;
        fib = fib1 + fib2;
        fib1 = fib2;
        fib2 = fib;
    }
 
    return fib1;
}
 
unsigned GCD(int a, int b)
{
    while (a - b)
        if (a > b) a -= b;
        else b -= a;
 
        return a;
}
 
int main()
{
    int ni, nj, nx;
    int fnx;
 
    std::cin >> ni >> nj;
    nx = GCD(ni, nj);
    fnx = fibonacci(nx) % 1000000000;
    std::cout << fnx << std::endl;
    return 0;
}

zer0mail · 15.08.2015, 14:27

Похоже, действительно лучше убить

А модуль используется здесь: res_2 %= mod;

@_Ivana · 15.08.2015, 14:29

Не по теме:

Сообщение от Melvil

В данной программе:

Melvil, держите плюс :) Хоть вы и не понимаете многих простых вещей, но зато привели в полубожеский вид форматирование кота Mr.X :)

@Melvil · 15.08.2015, 19:48 **[ТС]**

Сообщение от zer0mail

А модуль используется здесь: res_2 %= mod;

Вводим -5, получаем -5, где модуль?:

C++
1
2
3
4
5
6
7
8
9
10
#include <iostream>
using namespace std;
 
int main()
{
    int a;
    cin >> a;
    a %= 100000000;
    cout << a << endl;
}

@nonedark2008 · 15.08.2015, 20:21

Сообщение от Melvil

где модуль?

Под модулем подразумевается остаток от деление. Тык.

@Melvil · 15.08.2015, 20:29 **[ТС]**

Сообщение от nonedark2008

Под модулем подразумевается остаток от деление

Спасибо, теперь ясно.

@Чечулин Лев · 28.04.2019, 11:56

#include<bits/stdc++.h>
using namespace std;
int main ()
{
long long i,j;
cin>>i>>j;
while(i%j!=0&&j%i!=0)
{
if(i>j)i=i%j;
else j=j%i;
}
if(i>j)i=j;
else j=i;
vector<long long>v(i);
v[0]=1;
v[1]=1;
for(int t=2; t<i; t++)
{
v[t]=(v[t-2]+v[t-1])%1000000000;
}
cout<<v[i-1];
}

Я так писал

@Gonte · 21.08.2020, 12:23

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
vector<unsigned long long> fib(1000000);
void fibon(int n){
    fib[0]=0;
    fib[1]=1;
    for(int i=2;i<=n;i++){
        fib[i]=(fib[i-1]+fib[i-2])%1000000000;
    }
}
int main() {
    int n,m;
    cin>>n>>m;
    if(n<m){
        int t=m;
        m=n;
        n=t;
    }
    fibon(n);
    cout<<fib[__gcd(n,m)];
}

Новые блоги и статьи Все статьи Все блоги /
Эксперимент с картинкой-обложкой на CodinGame Adler 10.07.2026 Решил на днях провести эксперимент. У меня есть аккаунт на CodinGame, ТОП-3 по РФ среди 2200 участников (в разделе соревнования по программированию ИИ-ботов). Там есть обложка, куда можно влепить. . .	После бана на Пикабу не работает авторизация аккаунта с Яндекса. Hrethgir 09.07.2026 В частности https:/ / auto. ru/ logbook/ zapret-na-vozhdenie-posle-65-let_1cf28789-07b4-4c75-a2f7-4cd4edf9deeb тут хотел оставить комментарий такой Зрите в корень - монополизация на разработку программ. . .	GitDOS: Когда я решил скрестить MS-DOS, GitHub и Claude MaGz GoLd 08.07.2026 Привет, Киберфорум! Хочу поделиться своим проектом, который, надеюсь, вас заинтересует. GitDOS — это веб-приложение, которое позволяет запускать DOS в браузере с тремя крутыми фичами: диски живут в. . .	Учебный мини "цифровой двойник" = (Сервер = Java + Flask_питон )+(3D = Гугловскаая 4T nvideo + google colab) +( WMS = Odoo на Docker) anaschu 07.07.2026 Увидел в требованиях к вакансии создателя имитационных моделей связку (REst + Api + WMS + Anylogic + питон + 3D Nvideo), и решил посмотреть, что это такое. Из этого всего я работал более менее. . .
Море в объективе kumehtar 06.07.2026 Хотел написать много проникновенных слов, но передумал. Оно само - говорит. Кто слышит тот слышит.	Doom для терминала без стрельбы и монстров. 3D Raycasting на ascii. dcc0 05.07.2026 Попросил нейронную сеть deepai. org написать рейкастинг 3D с библиотекой ncurses для Linux. Чтобы можно было ходить на стрелочки. Чтобы стены были отрисованы символами. Справилась. Первый вариант. . .	Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .	Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .

zer0mail 2688 / 2260 / 244 Регистрация: 03.07.2012 Сообщений: 8,231 Записей в блоге: 1
	15.08.2015, 14:27
	Похоже, действительно лучше убить А модуль используется здесь: res_2 %= mod; 1

@Чечулин Лев 0 / 0 / 0 Регистрация: 28.04.2019 Сообщений: 1
	28.04.2019, 11:56
	#include<bits/stdc++.h> using namespace std; int main () { long long i,j; cin>>i>>j; while(i%j!=0&&j%i!=0) { if(i>j)i=i%j; else j=j%i; } if(i>j)i=j; else j=i; vector<long long>v(i); v[0]=1; v[1]=1; for(int t=2; t<i; t++) { v[t]=(v[t-2]+v[t-1])%1000000000; } cout<<v[i-1]; } Я так писал 0