Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.77/13: Рейтинг темы: голосов - 13, средняя оценка - 4.77
1480 / 944 / 811
Регистрация: 30.04.2016
Сообщений: 3,298
1

Вывод N-ого члена последовательности

02.08.2018, 18:03. Показов 2550. Ответов 25
Метки нет (Все метки)

Здравствуйте, уважаемые форумчане! У меня опять несложный вопрос к тем кто разбирается. С модулями у меня плохо, поэтому обращаюсь сюда. Сама задача совсем несложная, но мне бы очень хотелось получить опыт того как это обычно делается правильно. Дана последовательность: 3, 8, 12, 17, 22, 28, 35, ... Необходимо вывести ее n-ый член по модулю 123456789. Ограничения на n: 1<=n<=10^11. Мне удалось вывести первые n членов и сделал я это довольно быстро пользуясь только операцией сложения. Но мне непонятно (раньше таких задач не решал) куда вставлять операцию mod 123456789 в моем коде, чтобы все посчитать правильно и уложится в ограничения? Очень прошу помочь решить этот несложный вопрос. Вот код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
 
    using namespace std;
 
int main() {
    int n, a, b, sum, k;
    cin >> n;
    a = 3;
    b = 8;
    k = -1;
    while (n--) {
        cout << a << " ";
        sum = a + b - k;
        a = b;
        b = sum;
        k += 4;
    }
    system("pause");
    return 0;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.08.2018, 18:03
Ответы с готовыми решениями:

Вычисление n-ого члена Фибоначчи
Всем привет, реализовал задачу через динамический массив, как еще можно решить? (Я умею гуглить,...

Найти номер первого члена последовательности, который отличается от предыдущего члена не более чем на заданное значение
Рассмотрим последовательность, образованную дробями: 1/1, 2/1, 3/2, ..., в которой числитель...

Вывести на экран значения 0-ого, 3-ого и 13-ого битов числа n в формате short int
Задано число n в формате short int. Вывести на экран значения 0-ого, 3-ого и 13-ого битов...

В последовательности Фибоначчи найти индекс члена последовательности, удовлетворяющего условию
помогите не могу найти ошибку вводится число A,найти номер К такого числа Фибоначчи ,что...

25
Продавец времени
5779 / 3188 / 732
Регистрация: 12.03.2015
Сообщений: 15,100
02.08.2018, 18:28 2
Я хз, что точно имеется в виду, но мой телепатор мне говорит: "попробуй сначала так"
C++
1
2
3
#define ыкс 123456789
// ..... внутри цикла:
if (sum > ыкс) sum %= ыкс;
1
Эксперт C
26051 / 16244 / 3490
Регистрация: 24.12.2010
Сообщений: 35,595
02.08.2018, 18:45 3
Цитата Сообщение от Fixer_84 Посмотреть сообщение
куда вставлять операцию mod
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
 
    using namespace std;
 
int main() {
    int n, a, b, sum, k;
    int M = 123456789;
    cin >> n;
    a = 3;
    b = 8;
    k = -1;
    while (n--) {
        cout << a << " ";
        sum = (a + b - k)%M;
        a = b;
        b = sum;
        k = (k+4)%M;
    }
    system("pause");
    return 0;
}
Добавлено через 13 минут
Fixer_84, Вообще-то операцию "%" можно применить только к итоговой сумме. Логически (математически) это верно. Однако машинная арифметика не всегда подчиняется законам математики.
Хотя (a+b)%m = a%m + b%m абсолютно справедливое математическое равенство, при машинных вычислениях это может быть не так, если (a+b) вылезет за разрядную сетку. Поэтому, чем раньше мы возьмем остаток - тем лучше. И телепатор уважаемого Verevkin может оказаться не прав. Он неплохо знает математику, но, наверное, ему не приходилось моделировать бесконечность на конечном автомате
Короче. Сложение, вычитание и умножение перестановочны с операцией взятия остатка (дистрибутивность).
А называется все "гомомофизмом", точнее (в данном случае) "эпиморфизмом". Конечно, таких "умных" слов вы вполне можете не знать и прекрасно проживете все оставшуюся жизнь. Но это так - вдруг любопытство замучает...
1
1480 / 944 / 811
Регистрация: 30.04.2016
Сообщений: 3,298
02.08.2018, 19:05  [ТС] 4
Байт, здравствуйте! Спасибо за ваш ответ. Тогда уже для n >= 1000000 выдает отрицательный ответ, а должно быть n <= 10^11. Не знаю что делать. Вот код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
 
    using namespace std;
 
int main() {
    long long n, a, b, sum, k, result;
    cin >> n;
    a = 3;
    b = 8;
    k = -1;
    while (n--) {
        result = a;
        sum = (a + b - k) % 123456789;
        a = b;
        b = sum;
        k = (k + 4) % 123456789;
    }
    cout << "\nn-th => "<< result << "\n";
    system("pause");
    return 0;
}
Нужно, чтобы уже на промежуточных вычислениях числа маленькие получались, а не выходит...Может, я что-то делаю не так.

Добавлено через 14 минут
Байт, а нет, отправил код. Ошибок нет, но говорит time limit exceeded Вот ссылка: https://www.spoj.com/problems/ARD1/ Вот код при котором TLE:

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 <bits/stdc++.h>
 
    using namespace std;
 
int main() {
    long long n, a, b, sum, k, result, t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n;
        a = 3;
        b = 8;
        k = -1;
        while (n--) {
            result = a;
            sum = (a + b - k) % 123456789;
            a = b;
            b = sum;
            k = (k + 4) % 123456789;
        }
        cout << result << "\n";
    }
    system("pause");
    return 0;
}
0
Эксперт C
26051 / 16244 / 3490
Регистрация: 24.12.2010
Сообщений: 35,595
02.08.2018, 19:08 5
Попробуйте поставить после 123456789 LL.
Или даже так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
 
    using namespace std;
 
int main() {
    long long n, a, b, sum, k, result;
    cin >> n;
    a = 3;
    b = 8;
    k = -1;
    while (n--) {
        result = a;
        sum = (a + b - k) % (long long)123456789;
        a = b;
        b = sum;
        k = (k + 4) % (long long)123456789;
    }
    cout << "\nn-th => "<< result << "\n";
    system("pause");
    return 0;
}
1
1480 / 944 / 811
Регистрация: 30.04.2016
Сообщений: 3,298
02.08.2018, 19:59  [ТС] 6
Байт, да нет. Долго думает даже для n = 1000000000. А время 0.1 сек на выполнение. Тут какая-то формула нужна. Вычислять все члены последовательности слишком долго, даже по модулю, но я не уверен. В задании сказано, что значение n, вроде как, можно модифицировать для более хорошего решения.

Добавлено через 16 минут
Байт, но ведь нет четкого правила по которому такие формулы выводятся? Может быть, можно составить систему уравнений?

Добавлено через 12 минут
Байт, здесь рассказывается как можно построить систему уравнений, чтобы вывести формулу (полином): https://www.purplemath.com/modules/nextnumb.htm, но для этой последовательности у меня, пока, ничего не получается

Добавлено через 16 минут
Байт, может быть, нужно использовать рекуррентные соотношения? Тема остается открытой. Буду рад любой помощи по оптимизации данной задачи.
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
04.08.2018, 14:55 7
О мой Бог
Это же.. Ну нет ничего проще таких задач. Ну вот реально. Это настолько просто, что..
Если быстро и вкратце.
Составляем исходную матрицу (f0 f1 k 4)
Составляем матрицу, что жаждем получить (f1 f0+f1 k+4 4)
Составляем матрицу перехода P
Код
0 1 0 0 
1 1 0 0 
0 -1 1 0 
0 0 1 1
Получаем
(f0 f1 k 4) * P = (f1 f0+f1 k+4 4)
А если возвести матрицу перехода в N-ую степень
(f0 f1 k 4)* P^n = (fn fn+1 k 4)
Конец. Все. Нужно возвести P в степень. А потом умножить на исходную.
Дел на 5 минут
1
3413 / 2772 / 751
Регистрация: 25.03.2012
Сообщений: 10,080
Записей в блоге: 1
04.08.2018, 15:43 8
Ромаха, это какой-то сарказм?
Осталось превратить С++ в язык матричных вычислений, чтобы ваша матричная магия на нём писалась проще, чем единственный цикл по сложению скалярных переменных
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
04.08.2018, 16:17 9
Kuzia domovenok, а подумать?
Ограничения 10^11. Ваш цикл сработает за 0.1с?
Сложность моего решения 4^3*log(n)
И единственная "сложность" умножать матрицы.
0
1480 / 944 / 811
Регистрация: 30.04.2016
Сообщений: 3,298
04.08.2018, 17:13  [ТС] 10
Ромаха, спасибо за ваш ответ. Может быть, это просто для тех кто знает как это делается, например, для вас Но я через матрицы так ничего пока не вычислял, но я готов написать программу по вашему алгоритму. Нем могли бы вы, пожалуйста, более подробно (с примером) расписать что нужно делать. Матрицы я умножать и возводить в степень умею.
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
04.08.2018, 18:03 11
Fixer_84, а что из написанного не понятно? Там хорошо описанный алгоритм. Ну как по мне
0
190 / 164 / 82
Регистрация: 01.07.2016
Сообщений: 923
04.08.2018, 18:30 12
Ромаха, Здравствуйте, а можно узнать каким образом вы пришли к такому решению? Откуда взялась матрица перехода P и исходная матрица, на чём основывается ваше решение, проще говоря В ЧЁМ СМЫСЛ? Буду очень благодарен за внятное объяснение
0
1480 / 944 / 811
Регистрация: 30.04.2016
Сообщений: 3,298
04.08.2018, 19:31  [ТС] 13
Цитата Сообщение от Ромаха Посмотреть сообщение
Fixer_84, а что из написанного не понятно?
Мне не понятно, что есть исходная матрица (f0 f1 k 4), что есть матрица перехода P и самое главное, что будет ответом в матрице (fn fn+1 k 4), когда мы возведем матрицу перехода P в степень n и умножим на исходную? Вы не могли бы, пожалуйста, расписать с конкретными числами? Уж очень хочется дорешать задачу
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
04.08.2018, 22:19 14
Цитата Сообщение от no swear Посмотреть сообщение
Здравствуйте
Привет
Цитата Сообщение от no swear Посмотреть сообщение
каким образом вы пришли к такому решению?
Если честно - то оно очевидное.
Все(или почти все) задачи на последовательности решаются двумя путями - либо oeis.org (кстати, кому не лень. проверьте что там про это пишут. ибо мой интернет не может себе это позволить) либо вывод некой рекуррентной формулы. Тут пан Fixer ее вывел. И она есть маленькая модификация на числами Фибоначчи (и тут можно подумать, что можно высчитывать числа Фибоначчи и что-то делать с ними. Но это не так (может так и можно. но это, как по мне, слишком долгий путь с непонятной вероятностью успеха)
И тут в дело вступает фича с возведением матрицы в степень. Это довольно известный прием. Например, матрицей(смежности) в степени можно насчитать количество путей длины k.

Но эт лирика.
Про все это можно почитать, если погуглить.
Если, опять же вкратце.
Давай рассмотрим исходную матрицу.
(f0 f1 k0)
И матрицу, которую мы хотим получить
(f1 f2 k'), где f2 = f1+f2-k0, k' = k+4
Красота в том, что 1 можно легко заменить на i, и ничего не изменится. Т.е.
(f(i-1) fi ki) -> (fi f(i+1) k')
Внимание - это все еще матрицы. Да, размерность 1x3, но матрицы

Но теперь появляется проблема. Нам нужно найти такую матрицу P, чтобы (f(i-1) fi ki) x P = (fi f(i+1) k')
Можно, конечно, попробовать решить матричное уравнение. Но это чуточку нерационально
Давайте добавим еще одну размерность, куда просто затолкаем 4
Итак - (f0 f1 k0 4) x P = (f1 f1+f0 k0+4 4)
Конец и красота.
Так из (f0, f1, k) мы научились получать (f1, f2, k). Давай применим ту же самую матрицу перехода. И получим (f2, f3, k)
А теперь ((((f0 f1 k0 4) x P) x P) x P .... = (fn fn+1 k 4)
Но из-за ассоциативности умножения
(f0 f1 k0 4) x (P x P x P .. x P) = (fn fn+1 k 4)
(f0 f1 k0 4) x P^n = (fn fn+1 k 4)
Конец.
Цитата Сообщение от Fixer_84 Посмотреть сообщение
Вы не могли бы, пожалуйста, расписать с конкретными числами?
Нет. Это скучно и не нужно (или мне так кажется)
Цитата Сообщение от Fixer_84 Посмотреть сообщение
есть исходная матрица (f0 f1 k 4)
Вы не поверите, но нужно просто подставить изначальные f0 f1 k 4..
Где f0 = 3, f1 = 8, k = -1, 4 = 4
Классно, да?
Цитата Сообщение от Fixer_84 Посмотреть сообщение
что будет ответом в матрице (fn fn+1 k 4)
Этот вопрос реально стоит?
А если я сделаю (очевидное) уточнение, что fi - это i-ый элемент последовательности. А задача стоит найти n-ый?
2
1480 / 944 / 811
Регистрация: 30.04.2016
Сообщений: 3,298
04.08.2018, 23:29  [ТС] 15
Ромаха, я не совсем понял. Нам нужно найти n - ый член последовательности по модулю 123456789. Но n до 10^11. Разве возведение в такую степень не займет много времени?
0
190 / 164 / 82
Регистрация: 01.07.2016
Сообщений: 923
05.08.2018, 00:55 16
Цитата Сообщение от Fixer_84 Посмотреть сообщение
Разве возведение в такую степень не займет много времени?
Бинарный алгоритм возведения числа(или матрицы) в степень за lg(n)

Для n = 10^11 вам понадобится произвести всего лишь 35 операций умножения чтобы возвести число(или матрицу) в нужную вам степень что делается компом за очень-очень малое время
1
1480 / 944 / 811
Регистрация: 30.04.2016
Сообщений: 3,298
05.08.2018, 01:28  [ТС] 17
Цитата Сообщение от no swear Посмотреть сообщение
Для n = 10^11 вам понадобится произвести всего лишь 35 операций умножения чтобы возвести число(или матрицу) в нужную вам степень что делается компом за очень-очень малое время
no swear, спасибо за ваш ответ. Объясните, пожалуйста, как мы получаем степень матрицы P для n-ого члена последовательности?
0
190 / 164 / 82
Регистрация: 01.07.2016
Сообщений: 923
05.08.2018, 11:14 18
Цитата Сообщение от Ромаха Посмотреть сообщение
P^n
Цитата Сообщение от Fixer_84 Посмотреть сообщение
как мы получаем степень матрицы P для n-ого члена последовательности?
Перемножаем матрицу P на саму себя же но не как обычно мы это делаем (т е P*P*P*P...), а по алгоритму бинарного возведения в степень числа(для матрицы всё тоже самое). Получаем P^n, затем умножаем её на матрицу
Цитата Сообщение от Ромаха Посмотреть сообщение
(f0 f1 k0 4) x P^n
(f0 f1 k0 4) - матрица размерности 1x4 и получаем
Цитата Сообщение от Ромаха Посмотреть сообщение
(fn fn+1 k 4)
Вот формула целиком
Цитата Сообщение от Ромаха Посмотреть сообщение
(f0 f1 k0 4) x P^n = (fn fn+1 k 4)
2
1480 / 944 / 811
Регистрация: 30.04.2016
Сообщений: 3,298
05.08.2018, 17:02  [ТС] 19
Цитата Сообщение от Fixer_84 Посмотреть сообщение
Для n = 10^11 вам понадобится произвести всего лишь 35 операций умножения чтобы возвести число(или матрицу) в нужную вам степень что делается компом за очень-очень малое время
Я извиняюсь, но вы сказали, что нам понадобится всего лишь 35 операций. Вот программа, которая возводит матрицу в заданную степень. Теперь представьте, что она нужно получить 10000000000-ый член последовательности. Значит мы вводим матрицу P размерностью 4 x 4 и возводим в 1000000000-ую степень, правильно? При таком возведении типа данных long long будет достаточно?

0 1 0 0
1 1 0 0
0 -1 1 0
0 0 1 1

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 <bits/stdc++.h>
 
using namespace std;
 
//Данная программа возводит целочисленную квадратную матрицу в степень используя рекурсию
 
    void matrixInput(int** a, int n) { //Функция ввода матрицы
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> a[i][j];
            }
        }
    }
 
    int** matrixMultiply(int** a, int** b, int n) //Функция переменожения двух матриц
    {
        int** c = new int*[n];
        for (int i = 0; i < n; i++) {
            c[i] = new int[n];
        }
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) {
                c[j][i] = 0;
                for (int r = 0; r < n; r++) {
                    c[j][i] += a[j][r] * b[r][i];
                }
            }
        }
        return c;
        for (int i = 0; i < n; i++) {
            delete [] c[i];
        }
        delete [] c;
    }
    
    int** matrixPower(int** a, int n, int m) { //Бинарное возведение матрицы в степень (оптимизация)
    if (m == 1)
        return a;
    if (m % 2 == 1)
        return matrixMultiply(matrixPower(a, n, m - 1), a, n);
    else {
        a = matrixPower(a, n, m / 2);
        return matrixMultiply(a, a, n);
        }
    }
 
int main() {
    int n, power; //Объявляем две целочисленные переменные
    cout << "Enter a matrix size:\n";
    cout << "n = ";
    cin >> n; //Вводим размерность матрицы
    int** a = new int*[n]; //Объявляем двумерный целочисленный динамический массив (матрицу)   
    for (int i = 0; i < n; i++) {
        a[i] = new int[n];
    }
    cout << "Enter a matrix:\n";
    matrixInput(a, n); //Вводим матрицу
    cout << "Enter matrix power:\n";
    cout << "power = ";
    cin >> power; //Вводим степень в которую нужно возвести матрицу
    a = matrixPower(a, n, power); //Вызываем рекурсивную функцию и присваиваем результат 
    cout << "Target matrix:\n";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout.width(7);
            cout << a[i][j] << " "; //Выводим матрицу, возведенную в заданную степень
        }
        cout << "\n";
    }
    for (int i = 0; i < n; i++) { //Освобождаем память, выделенную под двумерный динамический массив
        delete [] a[i];
    }
    delete [] a;
    system("pause");
    return 0;
}
Добавлено через 55 минут
Ромаха, здравствуйте! Я реализовал ваш алгоритм (пока не редактировал программу, все в грубой форме через динамические массивы). Работает, правда, очень быстро, но я еще не отправлял. Вот код. Может быть, у вас будут какие-то замечания.

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
 
    using namespace std;
 
void matrixInput(long long** a, long long n) { //Функция ввода матрицы перехода
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
}
 
long long** matrixMultiply(long long** a, long long** b, long long n) //Функция переменожения двух матриц
{
    long long** c = new long long*[n];
    for (int i = 0; i < n; i++) {
        c[i] = new long long[n];
    }
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < n; i++) {
            c[j][i] = 0;
            for (int r = 0; r < n; r++) {
                c[j][i] += a[j][r] * b[r][i];
            }
        }
    }
    return c;
    for (int i = 0; i < n; i++) {
        delete[] c[i];
    }
    delete[] c;
}
 
long long** multiplyVector(long long** a, long long** b, long long n) //Функция умножения вектора на матрицу
{
    long long** c = new long long*[1];
    for (int i = 0; i < 1; i++) {
        c[i] = new long long[n];
    }
    for (int j = 0; j < 1; j++) {
        for (int i = 0; i < n; i++) {
            c[j][i] = 0;
            for (int r = 0; r < n; r++) {
                c[j][i] += a[j][r] * b[r][i];
            }
        }
    }
    return c;
    for (int i = 0; i < 1; i++) {
        delete[] c[i];
    }
    delete[] c;
}
 
long long** matrixPower(long long** a, long long n, long long m) { //Бинарное возведение матрицы в степень (оптимизация)
    if (m == 1)
        return a;
    if (m % 2 == 1)
        return matrixMultiply(matrixPower(a, n, m - 1), a, n);
    else {
        a = matrixPower(a, n, m / 2);
        return matrixMultiply(a, a, n);
    }
}
 
int main() {
    long long n, power;
    cout << "Enter a matrix size (n = 4):\n"; //Вводим размерность матрицы (n = 4)
    cout << "n = ";
    cin >> n;
    long long** a = new long long*[n];
    for (int i = 0; i < n; i++) {
        a[i] = new long long[n];
    }
    long long** b = new long long*[1];
    for (int i = 0; i < 1; i++) {
        b[i] = new long long[n];
    }
    long long** c = new long long*[1];
    for (int i = 0; i < 1; i++) {
        c[i] = new long long[n];
    }
    cout << "Enter a vector:\n"; //3 8 -1 4
    for (int j = 0; j < n; j++) {
        cin >> b[0][j];
    }
    cout << "Enter a matrix:\n"; //Вводим матрицу перехода
    matrixInput(a, n);
    cout << "Enter a matrix power (n-th member):\n";
    cout << "power = ";
    cin >> power;
    a = matrixPower(a, n, --power);
    c = multiplyVector(b, a, n);
    cout << "Searched vector:\n"; //Выводим искомую матрицу
    for (int j = 0; j < n; j++) {
        cout << c[0][j] << " ";
    }
    cout << "\nN-th element: " << c[0][0] << "\n"; //Выводим искомый член последовательности
    for (int i = 0; i < n; i++) {
        delete[] a[i];
    }
    delete[] a;
    for (int i = 0; i < 1; i++) {
        delete [] b[i];
    }
    delete [] b;
    for (int i = 0; i < 1; i++) {
        delete [] c[i];
    }
    delete [] c;
    system("pause");
    return 0;
}
0
190 / 164 / 82
Регистрация: 01.07.2016
Сообщений: 923
05.08.2018, 17:28 20
Цитата Сообщение от Fixer_84 Посмотреть сообщение
Теперь представьте, что она нужно получить 10000000000-ый член последовательности. Значит мы вводим матрицу P размерностью 4 x 4 и возводим в 1000000000-ую степень, правильно?
Да, совершенно верно.

Цитата Сообщение от Fixer_84 Посмотреть сообщение
При таком возведении типа данных long long будет достаточно?
Нет конечно
Поэтому после каждой операции умножения берите остаток от числа 123456789 которое задано у вас по условию задачи, и всё.

a^n mod b = (((((a mod b) * a) mod b) * a) mod b)...
2
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.08.2018, 17:28

Вывести значение n-ого элемента последовательности
Пусть есть набор чисел a 1 , a 2 , a 3 , … Предположим, что a 1 =10, a 2 =a 1 +(-1) 2 , a 3 =a 2...

Определение n-го члена последовательности
Вот сама последовательность: 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, ..

Нахождение n-го члена последовательности
Программу выполните с использованием цикла с предусловием и с использованием цикла с постусловием....

Рекурсия: вычисление n-го члена последовательности
Требуется разработать рекурсивную функцию, возвращающую значение для вычисления n-го члена...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.