Длинная арифметика. Факториал 1 <= n <= 10000

@Dennis Ritchie · Регистрация: 27.07.2014

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

Добрый вечер.
Подскажите, пожалуйста, возможно ли написать длинную арифметику для вычисления факториала до 10000 включительно на C++ без использования boost и т. д.? На python'e, например, это будет выглядеть так

:

Python
1
2
3
4
5
n = int(input())
a = 1
for i in range(2, n + 1):
    a *= i
print(a)

А что делать на C++?

@Dennis Ritchie · 04.03.2015, 01:46 **[ТС]**

Сообщение от Новичок

Не, вот так вроде работает...

Проверил в тестирующей системе (на сложение длинных чисел там тоже задача есть) на числах, состоящих из 10000 цифр. Программа прошла все тесты.

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

изо всей длинной арифметики здесь реализовано только умножение длинного числа на обычное, но этого для вычисления факториала вполне хватает

Программа проходит только 2 теста из 23. Что-то не так.

@Ромаха · 04.03.2015, 08:33

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
#include <stdio.h>
#include <string.h>
#define radix 10000
#define digits 4
#define size (10000 / digits + 1)
   
typedef struct
{
    int d[size], len;
} bignum_t;
   
void read_bignum (bignum_t *num)
{
    char s[size*radix];
    int i, j;
 
    strcpy (s, "1");
    num->len = 1;
    num->d[0] = 0;
   
    for (i = 0; s[i]; i++) {
        int cr = (s[i] - '0');
        for (j = 0; j < num->len; j++) {
            cr = num->d[j]*10 + cr;
            num->d[j] = cr % radix;
            cr /= radix;
        }
        if (cr > 0)
            num->d[num->len++] = cr;
    }
}
   
void write_bignum (bignum_t *num)
{
    int i;
    printf ("%d", num->d[num->len-1]);
    for (i = num->len-2; i >= 0; i--)
        printf ("%04d", num->d[i]);
}
   
int greatere (bignum_t *a, bignum_t *b)
{
    int i;
    if (a->len > b->len)
        return 1;
    else if (a->len < b->len)
        return 0;
   
    for (i = a-> len-1; i>0; i--)
        if (a->d[i] <= b->d[i])
            break;
   
    return a->d[i] > b->d[i];
}
   
bignum_t pr_bignum(bignum_t *a, int b)
{
    int i, cr = 0;
    bignum_t t;
      
    
    for (i = 0; i < a->len; i++) {
        cr += a->d[i] * b;
        t.d[i] = cr % radix;
        cr /= radix;
    }
     
    t.len = a->len;
    if (cr)
        t.d[t.len++] = cr;
   
    return t;
}
   
int main ()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout); 
      
    bignum_t a;
    int b, i;
 
     
    scanf ("%d", &b);
   
    if (b == 0) {
        printf ("1");
        return 0;
    }
     
    a.d[0] = b;
    a.len = 1;
    for (i = b-1; i > 1; i--)
        a = pr_bignum(&a, i);
    
    write_bignum (&a);
    return 0;
}

Вот.. Писалось давно и на Си

@Dennis Ritchie · 04.03.2015, 08:43 **[ТС]**

Ромаха, для 10000 не работает.

@Ромаха · 04.03.2015, 09:21

Нужно было всего-то размер увеличить..
Заодно потер не нужное..

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
#include <stdio.h>
#include <string.h>
#define radix 100000
#define digits 4
#define size (100000 / digits + 1)
   
typedef struct
{
    int d[size], len;
} bignum_t;
   
void write_bignum (bignum_t *num)
{
    int i;
    printf ("%d", num->d[num->len-1]);
    for (i = num->len-2; i >= 0; i--)
        printf ("%04d", num->d[i]);
}
   
 
bignum_t pr_bignum(bignum_t *a, int b)
{
    int i, cr = 0;
    bignum_t t;
      
    
    for (i = 0; i < a->len; i++) {
        cr += a->d[i] * b;
        t.d[i] = cr % radix;
        cr /= radix;
    }
     
    t.len = a->len;
    if (cr)
        t.d[t.len++] = cr;
   
    return t;
}
   
int main ()
{
    bignum_t a;
    int b, i;
 
     
    scanf ("%d", &b);
   
    if (b == 0) {
        printf ("1");
        return 0;
    }
     
    a.d[0] = b;
    a.len = 1;
    for (i = b-1; i > 1; i--)
        a = pr_bignum(&a, i);
    
    write_bignum (&a);
    return 0;
}

@Dennis Ritchie · 04.03.2015, 10:00 **[ТС]**

Сообщение от Ромаха

Нужно было всего-то размер увеличить..

Спасибо. Но я не могу понять, почему тестирующая система засчитывает решение на Python'е на 100%, а на C/C++ проходит только 2 теста из 23.
Вот можете сами проверить:
Факториал
Что не так в C++?

@Ромаха · 04.03.2015, 10:13

Сообщение от Dennis Ritchie

Что не так в C++?

Память.. Вы ее слишком много брали.. Отправляйте изначальный вариант и он зайдет на 100..

Добавлено через 2 минуты
Это чудо тоже на полный балл..

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
#include <stdio.h>
#include <string.h>
#define radix 10000
#define digits 4
#define size (10000 / digits + 1)
   
typedef struct
{
    int d[size], len;
} bignum_t;
   
void write_bignum (bignum_t *num)
{
    int i;
    printf ("%d", num->d[num->len-1]);
    for (i = num->len-2; i >= 0; i--)
        printf ("%04d", num->d[i]);
}
   
 
bignum_t pr_bignum(bignum_t *a, int b)
{
    int i, cr = 0;
    bignum_t t;
      
    
    for (i = 0; i < a->len; i++) {
        cr += a->d[i] * b;
        t.d[i] = cr % radix;
        cr /= radix;
    }
     
    t.len = a->len;
    if (cr)
        t.d[t.len++] = cr;
   
    return t;
}
   
int main ()
{
    bignum_t a;
    int b, i;
 
    scanf ("%d", &b);
   
    if (b == 0) {
        printf ("1");
        return 0;
    }
     
    a.d[0] = b;
    a.len = 1;
    for (i = b-1; i > 1; i--)
        a = pr_bignum(&a, i);
    
    write_bignum (&a);
    return 0;
}

@Dennis Ritchie · 04.03.2015, 10:25 **[ТС]**

Сообщение от Ромаха

Это чудо тоже на полный балл..

А почему мой компилятор факториал для 10000 не считает?

@Ромаха · 04.03.2015, 11:08

Был такой косяк.. Там малясь неверная оценка size..

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
#include <stdio.h>
#include <string.h>
#define radix 100000
#define digits 5
#define size 7132
 
typedef struct
{
    int d[size], len;
} bignum_t;
 
void write_bignum (bignum_t *num)
{
    int i;
    printf ("%d", num->d[num->len-1]);
    for (i = num->len-2; i >= 0; i--)
        printf ("%05d", num->d[i]);
}
 
 
bignum_t pr_bignum(bignum_t *a, int b)
{
    int i, cr = 0;
    bignum_t t;
 
 
    for (i = 0; i < a->len; i++) {
        cr += a->d[i] * b;
        t.d[i] = cr % radix;
        cr /= radix;
    }
 
    t.len = a->len;
    if (cr)
        t.d[t.len++] = cr;
 
    return t;
}
 
int main ()
{
    bignum_t a;
    int b, i;
 
    scanf ("%d", &b);
 
    if (b == 0) {
        printf ("1");
        return 0;
    }
 
    a.d[0] = b;
    a.len = 1;
    for (i = b-1; i > 1; i--)
        a = pr_bignum(&a, i);
 
    write_bignum (&a);
    return 0;
}

Такой код и правильно работает, и полный балл получает

@Dennis Ritchie · 04.03.2015, 11:17 **[ТС]**

Сообщение от Ромаха

Такой код и правильно работает, и полный балл получает

Ну вот теперь я полностью доволен.

Спасибо.

Новые блоги и статьи Все статьи Все блоги /
[golang] Угол между стрелками часов alhaos 12.05.2026 По заданным значениям часа и минуты необходимо определить значение меньшего угла между стрелками аналогового циферблата часов. import "math" func angleClock(hour int, minutes int) float64 { . . .	Debian 13: Установка Lazarus QT5 ВитГо 09.05.2026 Эта инструкция моя компиляция инструкций volvo https:/ / www. cyberforum. ru/ blogs/ 203668/ 10753. html и его же старой инструкции по установке Lazarus с gtk2. . .	Нейросеть на алгоритме "эстафета хвоста" как перспектива. Hrethgir 06.05.2026 На десерт, когда запущу сервер. Статья тут https:/ / habr. com/ ru/ articles/ 1030914/ . Автор я сам, нейросеть только помогает в вопросах которые мне не известны - не знаю людей которые знали-бы. . .	Асинхронный приём данных из COM-порта Argus19 01.05.2026 Асинхронный приём данных из COM-порта Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .
попытка написать игровой сервер на C++ pyirrlicht 29.04.2026 попытка написать игровой сервер на плюсах с открытым бесконечным миром. возможно получится прикрутить интерпретатор питон для кастомизации игровой логики. что есть на текущий момент:. . .	Контроль уникальности выбранного документа-основания при изменении реквизита Maks 28.04.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРемонтСпецтехники", разработанного в КА2. Задача: уведомлять пользователя, если указанная заявка (документ-основание). . .	Благородство как наказание Maks 24.04.2026 У хорошего человека отношения с женщинами всегда складываются трудно. А я человек хороший. Заявляю без тени смущения, потому что гордиться тут нечем. От хорошего человека ждут соответствующего. . .	Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .

@Dennis Ritchie 555 / 148 / 58 Регистрация: 27.07.2014 Сообщений: 2,446
	04.03.2015, 08:43 [ТС]
	Ромаха, для 10000 не работает. 0

Длинная арифметика. Факториал 1 <= n <= 10000

Решение