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

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

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

Показать сообщение отдельно
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
26.08.2011, 14:13     НОК для N чисел
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. Засчитано

 
Текущее время: 06:44. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru