2

Даны два целых положительных числа M, N. Требуется найти все «дружественные» пары чисел на отрезке [M; N]. Дружественным для числа А является такое число В, что оно равно сумме делителей А, исключая само значение А. И наоборот, сумма делителей В, исключая В, равняется А. A не равно B.

Input
Со стандартного устройства ввода в первой строке через пробел вводятся два целых положительных числа M (2<=M<=105 ) и N (2<=M<=N<=105 ).
Output
Требуется вывести все пары «дружественных» чисел, расположенные на отрезке [M; N]. Пару «дружественных» чисел (E, F) нужно выводить раньше пары «дружественных» чисел (K, P), когда минимальный элемент пары «дружественных» чисел (E, F) меньше минимального элемента пары «дружественных» чисел (K, P). Число E в паре «дружественных» чисел (E, F) нужно выводить раньше числа F из этой же пары, когда Е меньше F. Числа в паре нужно разделять пробелом, ставить пробел после второго члена пары не нужно.

Sample Input

210 294

Sample Output

220 284
Примечание
Попробуйте реализовать функцию getSumOfDivisors(n), которая принимает число n, а возвращает сумму делителей числа n, кроме самого n.

Мой код

#include <stdio.h>
#include <math.h>
int getSumOfDivirsors(int a)
{
    int i,p;
    p = 1;
    for (i = 2; i <= a / 2; i++)
        if (a % i == 0) p = p + i;
    return p;
}
int main()
{
    int m, n, e, f, i, tr1, tr2;
    scanf("%d%d", &m, &n);
    if (m < 220) m = 220;
    if (n > 88730) n = 88730;

    for (i = m; i < n; i++)
    {
        tr1 = getSumOfDivirsors(i);
        if (tr1 <= n) {
            tr2 = getSumOfDivirsors(tr1);
            if (i == tr2 && tr1!=tr2) { printf("%d %d", tr2, tr1); printf("\n"); i = tr1; }

        }
        
    }
}

Выходит за временные рамки в 1с. Как можно улучшить код, чтобы укладывался в 1с ?

4
  • До 10^5 всего 5 пар дружественных чисел. Рекомендую не заморачиваться, жестко их прошить и выбирать потом подходящие...
    – Harry
    28 дек 2021 в 9:12
  • пустую команду в цикле убрать надо. for (i = 2; i <= a / 2; i++) ;
    – AlexGlebe
    28 дек 2021 в 9:12
  • @Harry А 10 в 5 это же 100000 28 дек 2021 в 9:21
  • Ну, значит 14 пар... Тем более! :)
    – Harry
    28 дек 2021 в 11:00

2 ответа 2

5

Берем функцию поиска суммы делителей

int getSumOfDivirsors(int a)
{
    int i,p;
    p = 1;
    for (i = 2; i <= a / 2; i++)
        if (a % i == 0) p = p + i;
    return p;
}

и понимаем, что она на самом деле делает дармовую работу. ведь если x есть делителем a, то a/x - это тоже делитель. Поэтому, можно считать до корня квадратного и тем самым ускорить неплохо. (с линейной сложности переходим на "корень квадратный")

int getSumOfDivirsors(int a)
{
    int p = 1;
    for (int i = 2; i <= sqrt(a);i++) {
        if (a % i == 0) p = p + i + a/i;
    }
    return p;
}

если предыдущий вариант в диапазоне 0-50000 у меня работал за 6 секунд, то с исправлениями - меньше пол секунды. До 10000 досчитал за 0.6.

update:

Чуточку помедитировал над функцией и нашел один случай, когда она работает не совсем верно - если исходное число - квадрат, тогда делитель, равный корню повторяется дважды. Я сильно сомневаюсь, что минусатор это увидел, но я увидел. Вот подправленный вариант.

int getSumOfDivirsors2(int a)
{
    int p = 1;
    int sq = sqrt(a);
    for (int i = 2; i < sq;i++) {
        if (a % i == 0) p = p + i + a/i;
    }
    if (sq*sq == a) { p = p+sq;}
    return p;
}

теперь результаты выдает более правильные.

3
  • sqrt(a) лучше вынести из цикла. Только константа, конечно, но всё же правильный обычай. 29 дек 2021 в 16:45
  • я решил проверить Ваше предположение, но обнаружил удивительное. после выноса константы, код цикла стал ... больше. Более того, даже без оптимизаций, clang сам додумался вынести вычисление sqrt за пределы цикла. Бенчмарки показали соизмеримую скорость и погрешность в несколько процентов. Скорее всего clang увидел, что у меня переменная не изменяется.
    – KoVadim
    29 дек 2021 в 22:04
  • "На компилятор надейся, а сам не плошай." :) Вы правы - этот код не проблема для оптимизатора. Он понимает что sqrt чистая функция, а a константа. 29 дек 2021 в 22:30
-1

В вашем коде есть ошибка в операторе i = tr1;. Например для отрезка 63020 76084 ваша программа выдаст одну пару 63020 76084, а должна выдать три 63020 76084, 66928 66992, 67095 71145. Убирайте присвоение - это не оптимизация, а ошибка.

В остальном ваш код рабочий, но работает медленее чем мог бы. getSumOfDivirsors можно серьёзно ускорить.

Сумма делителей натурального числа обладает одним интересным свойством. Обозначим через s(n) искомую сумму. В эту сумму включается и единица и само число. Почему так сейчас станет ясно.

Пусть n делится на простое p. Тогда можем записать что n = p^s * m, причём m на p уже не делится. Пусть k делитель m. Какие из него можно составить делители n? 1 * k, p * k, p^2 * k, ..., p^s * k. Их сумма равна (1 + p + p^2 + ... + p^s) * k. И так для любого делителя m. Переберём все делители m, для каждого сосчитаем такую сумму, все такие суммы сложим. Получится

(1 + p + p^2 + ... + p^s) * <сумма всех делителей m> =
= (1 + p + p^2 + ... + p^s) * s(m)

В этой сумме перечислены по одному разу все делители n. Значит

s(n) = (1 + p + p^2 + ... + p^s) * s(m)

Эта формула открывает очень быстрый способ сосчитать s(n) по разложению n на простые.

Нас интересуют все делители кроме самого числа, которое в s(n) включено. То есть нам нужна величина s(n) - n.

Подробнее тут: функция делителей.

Расчёт по этим формулам быстрее простого перебора делителей для составных n. Для простых n формула делает sqrt(n) проверок.

Можно сделать ещё быстрее, но и этого пока достаточно, чтобы программа уложилась в ограничения по времени с запасом.

#include <stdio.h>

int sum_of_divisors(int n) {
    int s = 1;
    int i = 2;
    int j = n;

    while (i * i <= j) {
        if (j % i == 0) {
            int f = 1;  // 1 + i + i^2 + ... + i^s
            int m = i;  // i, i^2, ..., i^s
            do {
                f += m;
                j /= i;
                m *= i;
            } while (j % i == 0);
            s *= f;
        }
        i += 1;
    }
    if (j > 1) {
        s *= 1 + j;
    }
    return s;
}

int sum_of_proper_divisors(int n) {
    return sum_of_divisors(n) - n;
}

int main()
{
    int m, n;
    if (scanf("%d %d", &m, &n) != 2) {
        return 1;
    }

    for (int i = m; i < n; ++i) {
        int j = sum_of_proper_divisors(i);
        if (i < j && j <= n && sum_of_proper_divisors(j) == i) {
            printf("%d %d\n", i, j);
        }
    }
}
$ gcc -std=c17 -pedantic -Wall -Wextra -Werror -O3 amicable-numbers.c 

$ time echo 1 100000 | ./a.out 
220 284
1184 1210
2620 2924
5020 5564
6232 6368
10744 10856
12285 14595
17296 18416
63020 76084
66928 66992
67095 71145
69615 87633
79750 88730

real  0m0.032s
user  0m0.028s
sys   0m0.000s

$ time echo 1 1000000 | ./a.out | wc -l
40

real  0m0.720s
user  0m0.716s
sys   0m0.000s

$ time echo 1 10000000 | ./a.out | wc -l
100

real  0m17.049s
user  0m17.044s
sys   0m0.000s

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.