Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

НОК для N чисел - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Принятие русского шрифта в консоли http://www.cyberforum.ru/cpp-beginners/thread345078.html
Здрасте! Я написал програму, которая должна использовать русский шрифт, но она его не распознает. Для того, что бы она отображала русский текст, я добавил команду setlocale( LC_ALL,"Russian" ); но...
C++ Переменные среды Windows Как в c++ использовать переменные среды windows? Например я хочу открыть текстовый файл в каталоге C:\documents and settings\user\1.txt Переменная среда данного каталога выглядит вот так:... http://www.cyberforum.ru/cpp-beginners/thread345058.html
Набор для программирования C++
Доброе время суток. Я хочу написать программу на С++. И затем продать ее. У меня нет денег покупать IDE,потому хочу отдельно взять компилятор, отдельно набор классов для GUI и т.д. Подскажите,...
Сформировать массив из элементов матрицы C++
Дан двумерный массив. Сформировать одномерный массив,каждый элемент которого равен количеству элементов соответствующего столбца двумерного массива,больших числа n
C++ Простая задача? http://www.cyberforum.ru/cpp-beginners/thread344988.html
Здравствуйте! После участия в ДЛКШ я понял, что очень много не знаю даже о самых элементарных вещах в Си\Си++. Например, обыкновенная простая задача на теорию вероятностей - Цветные шары В урне...
C++ Компилятор не видит vector #include <vector> using std::vector; vector<double> v; выбивает ошибку вектор не стд, вектор не определён. подскажите плз почему так может быть Во-первых, по правилам форума один вопрос - одна... подробнее

Показать сообщение отдельно
Thinker
Эксперт С++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
26.08.2011, 14:13
morphling, если задача из e-olimp, то без длинной арифметики не обойтись. Могу предложить свой вариант (проходит все тесты). Только код не оптимизирован (это можете вы проделать).

Вот

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <stdio.h>
#define Q 10000  // система счисления
#define N 100000
 
typedef int DIGIT;
int count[101];
DIGIT a[N], b[N];
int alen, blen;
 
// вывод конечного результата
void Print(DIGIT *a, int n)
{
   int i;
   for (i = n - 1; i >=0 ; i--)
      printf("%d", a[i]);
   printf("\n");
}
 
// нахождение максимальных степеней простых чисел
void Count(unsigned int n)
{
  unsigned int i;
  int a[101] = {0};
  i = 2;
  while (n != 1)
  {
      if (n % i == 0)
      {
          a[i]++;
          n /= i;
      }
      else
          if (i*i > n)
             i = n;
          else i++;
  }
  for (i = 1; i < 101; i++)
     if (a[i] > count[i])
        count[i] = a[i];
}
 
// сумма (длинная арифметика, числа перевернуты)
void Sum(DIGIT *a, int *alen, DIGIT *b, int *blen)
{
   DIGIT ost, buf;
   int i;
   i = ost = 0;
   while (i < *alen && i < *blen)
   {
       buf = (a[i] + b[i] + ost) / Q;
       a[i] = (a[i] + b[i] + ost) % Q;
       ost = buf;
       i++;
   }
   while (i < *alen)
   {
      buf = (a[i] + ost) / Q;
      a[i] = (a[i] + ost) % Q;
      ost = buf;
      i++;
   }
   while (i < *blen)
   {
      buf = (b[i] + ost) / Q;
      a[i] = (b[i] + ost) % Q;
      ost = buf;
      i++;
   }
   if (ost)
      a[i++] = ost;
   *alen = i;
}
 
// произведение (длинная арифметика, числа перевернуты)
void Product(DIGIT *a, int *alen, DIGIT *b, int blen)
{
   int i, j, buflen, prodlen = 0;
   DIGIT prod[N] = {0}, buf[N], ost;
   for (i = 0; i < blen; i++)
   {
      for (j = 0; j < i; j++)
         buf[j] = 0;
      ost = 0;
      for (j = 0; j < *alen; j++)
      {
         buf[i + j] = (a[j] * b[i] + ost) % Q;
         ost = (a[j] * b[i] + ost) / Q;
      }
      buflen = i + j;
      if (ost)
         buf[buflen++] = ost;
      Sum(prod, &prodlen, buf, &buflen);
   }
   for (i = 0; i < prodlen; i++)
      a[i] = prod[i];
   *alen = prodlen;
}
 
// перевод числа в массив в перевенутом виде
void ToArray(long x, DIGIT *a, int *n)
{
   int i = 0;
   do
   {
       a[i++] = x % Q;
       x /= Q;
   }
   while (x);
   *n = i;
}
 
 
int main()
{
  unsigned int n, i, j;
  unsigned int A[21];
 
  scanf("%u", &n);
  for (i = 0; i < n; i++)
  {
     scanf("%u", &A[i]);
     Count(A[i]);
  }
  ToArray(1, a, &alen);
  for (i = 1; i < 101; i++)
  {
     ToArray(i, b, &blen);
     for(j = 0; j < count[i]; j++)
        Product(a, &alen, b, blen);
  }
 
  Print(a, alen);
  return 0;
}


Добавлено через 43 минуты

Не по теме:


Среднее время выполнения: 0.016 секунды
Максимальное время выполнения: 0.031 секунды из 1 секунда, 3.1%
Лимит памяти: 1456 KB из 65536 KB, 2.2%
Результат по тестам:
1. Засчитано 2. Засчитано 3. Засчитано 4. Засчитано 5. Засчитано 6. Засчитано 7. Засчитано 8. Засчитано 9. Засчитано 10. Засчитано 11. Засчитано

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