Не понимаю, где ошибка

@CMson · Регистрация: 31.01.2013

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

Доброго времени суток!
Решаю задачу с тимуса, вот условие: http://acm.timus.ru/problem.aspx?space=1&num=1118

Не понимаю, где ошибка.. Подскажите.

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
#include <iostream>
 
int TrivialityOfNumbers(int num1, int num2) {
  int N;
  int n = num2 - num1 + 1;
  double* arr;
  float sumOfDivisors;
  float* trivialityOfNum;
  trivialityOfNum = new float[n];
  arr = new double[n];
  int i = 0;
  for (int j = num1; j <= num2; j++) {
    arr[i] = j;
    double sq = sqrt(arr[i]);
    sumOfDivisors = 1;
    for (int k = 2; k <= sq; k++) {
      if (j % (k) == 0)
        sumOfDivisors = sumOfDivisors + k;
    }
    trivialityOfNum[i] = sumOfDivisors / j;
    i = i + 1;
  }
  float min = trivialityOfNum[0];
  for (int j = 0; j < n; j++) {
    if (trivialityOfNum[j] < min) {
      min = trivialityOfNum[j];
      N = arr[j];
    }
  }
  return N;
  delete[] arr;
  delete[] trivialityOfNum;
}
 
// Главная функция
void main()
{
  int I, J, N;
  std::cin >> I >> J;
  int i = J - 1000;
  if (I == 1) {
    N = 1;
  }
  else if (I > J) {
    N = 0;
  }
  else if (I == J) {
    N = I;
  }
  else {
    if (I >= 1 && I <= 1000000 && J >= 1 && J <= 1000000) {
      if (i > I) {
        N = TrivialityOfNumbers(i, J);
      }
      else {
        N = TrivialityOfNumbers(I, J);
      }
    }
    else
      N = 0;
  }
  std::cout << N;
}

@Dani · 12.11.2014, 19:54

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

for (int k = 2; k <= sq; k++) {
* * * if (j % (k) == 0)
* * * * sumOfDivisors = sumOfDivisors + k;

Не только, если j % k == 0, то будет 2 делителя: k и j / k (если k * k != j)

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

sqrt(arr[i]);

sqrt(4) может быть 1.999999, поэтому лучше брать round(sqrt(j)) или можно условие в цикле сделать такое: k * k <= j

@CMson · 12.11.2014, 20:03 **[ТС]**

Спасибо, этого я не учла.
Но на первом же тесте программа все равно проваливается в тимусе..

@Dani · 12.11.2014, 20:21

Новый код в студию.

@CMson · 12.11.2014, 20:36 **[ТС]**

Сейчас у меня ощущение, что я не правильно Вас поняла насчет условия.

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
int TrivialityOfNumbers(int num1, int num2) {
  int N;
  int n = num2 - num1 + 1;
  double* arr;
  float sumOfDivisors;
  float* trivialityOfNum;
  trivialityOfNum = new float[n];
  arr = new double[n];
  int i = 0;
  for (int j = num1; j <= num2; j++) {
    arr[i] = j;
    sumOfDivisors = 1;
    for (int k = 2; k*k <= j; k++) {
      if (j % (k) == 0)
        sumOfDivisors = sumOfDivisors + k;
    }
    trivialityOfNum[i] = sumOfDivisors / j;
    i = i + 1;
  }
  float min = trivialityOfNum[0];
  for (int j = 0; j < n; j++) {
    if (trivialityOfNum[j] < min) {
      min = trivialityOfNum[j];
      N = arr[j];
    }
  }
  return N;
  delete[] arr;
  delete[] trivialityOfNum;
}
 
void main()
{
  int I, J, N;
  std::cin >> I >> J;
  int i = J - 1000;
  if (I == 1) {
    N = 1;
  }
  else if (I > J) {
    N = 0;
  }
  else if (I == J) {
    N = I;
  }
  else {
    if (I >= 1 && I <= 1000000 && J >= 1 && J <= 1000000) {
      if (i > I) {
        N = TrivialityOfNumbers(i, J);
      }
      else {
        N = TrivialityOfNumbers(I, J);
      }
    }
    else
      N = 0;
  }
  std::cout << N;
}

Добавлено через 7 минут
А еще при наличия корня, тривиальность числа считается неправильно.
Я явно что-то делаю не так.

@Dani · 12.11.2014, 20:41

Новый код в студию.

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

for (int k = 2; k*k <= j; k++) {
* * * if (j % (k) == 0)
* * * * sumOfDivisors = sumOfDivisors + k;

Тут вот: до корня только берутся делители, а чтобы брались все, то нужно брать не только k, но и j / k.

@CMson · 12.11.2014, 20:47 **[ТС]**

Ох..Теперь тривиальность считает правильно..да, исправила.
Только теперь на пятом тесте вылетает с неправильным результатом

Что работает не правильно - совершенно не понятно.

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
#include <iostream>
 
// Ищем тривиальность чисел в диапозоне от I до J
int TrivialityOfNumbers(int num1, int num2) {
  int N;
  int n = num2 - num1 + 1;
  double* arr;
  float sumOfDivisors;
  float* trivialityOfNum;
  trivialityOfNum = new float[n];
  arr = new double[n];
  int i = 0;
  for (int j = num1; j <= num2; j++) {
    arr[i] = j;
    sumOfDivisors = 1;
    for (int k = 2; k*k <= j; k++) {
      if (j % (k) == 0)
        sumOfDivisors = sumOfDivisors + k + (j/k);
    }
    trivialityOfNum[i] = sumOfDivisors / j;
    i = i + 1;
  }
  float min = trivialityOfNum[0];
  for (int j = 0; j < n; j++) {
    if (trivialityOfNum[j] < min) {
      min = trivialityOfNum[j];
      N = arr[j];
    }
  }
  delete[] trivialityOfNum;
  return N;
  delete[] arr;
}
 
// Главная функция
void main()
{
  int I, J, N;
  std::cin >> I >> J;
  int i = J - 1000;
  if (I == 1) {
    N = 1;
  }
  else {
    if (I >= 1 && I <= 1000000 && J >= 1 && J <= 1000000 && J > I) {
      if ((i) > I) {
        N = TrivialityOfNumbers(i, J);
      }
      else {
        N = TrivialityOfNumbers(I, J);
      }
    }
    else
      N = 0;
  }
  std::cout << N;
}

@Dani · 12.11.2014, 21:03

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

Что работает не правильно - совершенно не понятно.

Я же уже писал: если j = k * k, то если писать так
sumOfDivisors = sumOfDivisors + k + (j/k)
то делитель k посчитается в сумме 2 раза

@CMson · 12.11.2014, 21:19 **[ТС]**

Так будет правильно?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
...
  for (int j = num1; j <= num2; j++) {
    arr[i] = j;
    double sq = sqrt(j);
    sumOfDivisors = 1;
    for (int k = 2; k < sq; k++) {
      if (j % (k) == 0) {
        sumOfDivisors = sumOfDivisors + k;
        int ii = j / k;
        if (ii != k)
          sumOfDivisors = sumOfDivisors + ii;
      }
    }
...

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .

@CMson 3 / 3 / 4 Регистрация: 31.01.2013 Сообщений: 98
	12.11.2014, 20:03 [ТС]
	Спасибо, этого я не учла. Но на первом же тесте программа все равно проваливается в тимусе.. 0

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	12.11.2014, 20:21
	Новый код в студию. 0