Определить сколько существует пар чисел, которые в сумме (по правилам планеты Олимпия) дают число Х

@_Milk_ · Регистрация: 16.01.2018

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

Мегапопулярный Дзидзьо посетил планету Олимпия, где живет много поклонников спорта.
Тяжелая атлетика - наиболее популярная среди жителей Олимпии. Дзидзьо, пылкий поклонник этого
вида спорта, не раз был судьей на соревнованиях.

Интересно, что на этой планете и очень странные правила подсчета суммы двух чисел. Так, суммой двух
цифр считают наименьшее общее кратное этих чисел. Наименьшее общее кратное натуральных
чисел а и b - это такое наименьшее натуральное число, которое делится нацело на а и b, то есть сумма 2 и 4
это совсем не 6, а 4. В тяжелой атлетике правила определения победителя довольно просты: есть два упражнения
за каждую из которых даются определенные баллы в виде положительного целого числа. У кого больше сумма
баллов, тот и выиграет.

Однажды, во время соревнований по тяжелой атлетике, Дзидзьо сумел записать только сумму Х победителя. Теперь его интересует, сколько существует таких пар чисел, в сумме (по правилам планеты
Олимпия) дают число Х.

входные данные:

В первом и единственном строке задано целое число Х - сумма двоеборья спортсмена.

Вывести:
1 число - ответ на задачу
Примеры:
1.stdin: 47 stdout:3
2.stdin:6 stdout:9

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

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
#include <iostream>
#include <math.h>
using namespace std; 
bool prostoNumer(int n);
long gcd08(long a, long b);
int main()
{
    long m, n, x, i, j,  nsk,nsd, k=0;
    cin >> x; if (prostoNumer(x)) {
        cout << "3";
    }
    else {
        for (i = 1; i <= x; i++) {
            for (j = 1; j <= x; j++) {
 
                m = i; n = j;
                nsd = gcd08(m, n);
                nsk = (i*j) / nsd;
                if (nsk == x) { k++; }
            }
        }
 
        cout << k << endl;
    }
    //system("pause");
}
long gcd08(long a, long b) {
    long nod = 1L;
    long tmp;
    if (a == 0L)
        return b;
    if (b == 0L)
        return a;
    if (a == b)
        return a;
    if (a == 1L || b == 1L)
        return 1L;
    while (a != 0 && b != 0) {
        if (((a & 1L) | (b & 1L)) == 0L) {
            nod <<= 1L;
            a >>= 1L;
            b >>= 1L;
            continue;
        }
        if (((a & 1L) == 0L) && (b & 1L)) {
            a >>= 1L;
            continue;
        }
        if ((a & 1L) && ((b & 1L) == 0L)) {
            b >>= 1L;
            continue;
        }
        if (a > b) {
            tmp = a;
            a = b;
            b = tmp;
        }
        tmp = a;
        a = (b - a) >> 1L;
        b = tmp;
    }
    if (a == 0)
        return nod * b;
    else
        return nod * a;
}
bool prostoNumer(int n) {
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0)
            return false;
    return true;
}

пробовал так но по ограничению 1 сек не проходит

Байт · 26.01.2018, 14:38

_Milk_, зачем же вы перебираете все числа? Это и впрямь весьма затратно. Интересны только те, которые являются делителями x

C++
1
2
3
4
5
for (i = 1; i <= x; i++) {
     if (x%i) continue;
     for (j = 1; j <= x; j++) {
       if (x%j) continue;
      ....

Это не единственная и не самая "крутая" оптимизащия перебора...
Следующий шаг может заключаться в замене вложенного цикла на

C++
1
for(j=i; j<=x/i; j++)

но и это не предел.

@_Milk_ · 26.01.2018, 15:47 **[ТС]**

Но например х=6 тогда i=1 j=6 and i=6 j=1 ето два разних решения

Байт · 26.01.2018, 16:50

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

ето два разних решения

Ну и что?

C++
1
2
3
// после того как решение (i, j) найдено
if (j==i) k++;
else k += 2;

@_Milk_ · 27.01.2018, 14:45 **[ТС]**

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
#include <iostream>
#include <math.h>
using namespace std; 
bool prostoNumer(int n);
long gcd08(long a, long b);
int main()
{
    long m, n, x, i, j,  nsk,nsd, k=0;
    cin >> x; if (prostoNumer(x)) {
        cout << "3";
    }
    else {
        for (i = 1; i <= x; i++) {
            if (x%i) continue;
            else {
                for (j = i; j <= x / i; j++)
                {
                    if (x%j) continue;
                    else {
                        m = i; n = j;
                        nsd = gcd08(m, n);
                        nsk = (i*j) / nsd;
                        if (nsk == x) { k +=2; }
                    }
                }
            }
        }
 
        cout << k << endl;
    }
    system("pause");
    return 0;
}
long gcd08(long a, long b) {
    long nod = 1L;
    long tmp;
    if (a == 0L)
        return b;
    if (b == 0L)
        return a;
    if (a == b)
        return a;
    if (a == 1L || b == 1L)
        return 1L;
    while (a != 0 && b != 0) {
        if (((a & 1L) | (b & 1L)) == 0L) {
            nod <<= 1L;
            a >>= 1L;
            b >>= 1L;
            continue;
        }
        if (((a & 1L) == 0L) && (b & 1L)) {
            a >>= 1L;
            continue;
        }
        if ((a & 1L) && ((b & 1L) == 0L)) {
            b >>= 1L;
            continue;
        }
        if (a > b) {
            tmp = a;
            a = b;
            b = tmp;
        }
        tmp = a;
        a = (b - a) >> 1L;
        b = tmp;
    }
    if (a == 0)
        return nod * b;
    else
        return nod * a;
}
bool prostoNumer(int n) {
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0)
            return false;
    return true;
}

то есть так?

Добавлено через 2 часа 12 минут

Сообщение от Байт

Ну и что?

C++
1
2
3
// после того как решение (i, j) найдено
if (j==i) k++;
else k += 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
#include <iostream>
#include <math.h>
using namespace std;
bool prostoNumer(int n);
 
int main() {
    int x, i, k = 0, j;
    cin >> x;
    if (prostoNumer(x)) { cout << ("3"); }
    else {
        for (i = 1; i <= x; i++) {
            if (x%i != 0) { continue; }
            else {
                for (j = 1; j <= x / i; j++) {
                    if (x%j != 0) { continue; }
                    else {
                        if (j == i) { k++; }
                        else { k += 2; }
                    }
                }
 
            }
        }
        cout << k/2;
    }
    
    
}
bool prostoNumer(int n) {
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0)
            return false;
    return true;
}

по идее так?

Байт · 27.01.2018, 15:10

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

по идее так?

Да, похоже. Пробовали?
Только вот еще одно замечание
Ситуация i==j и при этом НОК(i, j) = x может возникнуть только в случае i == j == x

@_Milk_ · 27.01.2018, 15:14 **[ТС]**

Сообщение от Байт

Да, похоже. Пробовали?
Только вот еще одно замечание
Ситуация i==j и при этом НОК(i, j) = x может возникнуть только в случае i == j == x

К сожалению дает неправильный результат например я ввожу 6 должен быть результат 9 а выдает 18

Байт · 27.01.2018, 16:19

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

К сожалению дает неправильный результат

К сожалению, в данный момент не могу заняться вашей задачей. Или подождите до вечера, или попробуйте пока сами. Там надо просто повнимательнее посмотреть арифметику...

@_Milk_ · 27.01.2018, 16:32 **[ТС]**

Сообщение от Байт

К сожалению, в данный момент не могу заняться вашей задачей. Или подождите до вечера, или попробуйте пока сами. Там надо просто повнимательнее посмотреть арифметику...

окей

Добавлено через 2 минуты
Если можете посмотреть буду очень благодарен

Байт · 27.01.2018, 17:48

_Milk_, Посмотрите этот код. Кажется, ничего не упустил

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
#include <stdio.h>
#include <stdlib.h>
 
long gcd(long a, long b)  // Наибольший общий делитель
{ long t;
   while(1) {
     if (a < b) { t = a; a = b; b = t; }
     a = a % b;
     if (a==0) return b;
   }
}
int main(int ac, char *av[])
{ long X = 12; long i, j, k = 1, g;
  if (ac > 1) X = atol(av[1]); // вместо cin >> ввод через параметр командной строки
  printf("X=%ld\n% ld-%ld\n", X, X, X); // X-X - всегда будет решением
  for(i=1; i <= X/2; i++) {
    if (X%i) continue;
    for(j=i+1; j <=X; j++) {
      if (X%j) continue;
      g = gcd(j, i);
      if (g*X == i*j) {
        printf(" %ld-%ld %ld-%ld\n", i, j, j, i);  // Промежуточная выдача
        k += 2;
      }
    }
  }
  printf("k=%ld\n", k);
  return 0;
}

Несколько странной мне показалась функция gcd08, я ее заменил. И как будто здесь ни при чем определение простоты числа...

@_Milk_ · 27.01.2018, 18:14 **[ТС]**

Сообщение от Байт

_Milk_, Посмотрите этот код. Кажется, ничего не упустил

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
#include <stdio.h>
#include <stdlib.h>
 
long gcd(long a, long b)  // Наибольший общий делитель
{ long t;
   while(1) {
     if (a < b) { t = a; a = b; b = t; }
     a = a % b;
     if (a==0) return b;
   }
}
int main(int ac, char *av[])
{ long X = 12; long i, j, k = 1, g;
  if (ac > 1) X = atol(av[1]); // вместо cin >> ввод через параметр командной строки
  printf("X=%ld\n% ld-%ld\n", X, X, X); // X-X - всегда будет решением
  for(i=1; i <= X/2; i++) {
    if (X%i) continue;
    for(j=i+1; j <=X; j++) {
      if (X%j) continue;
      g = gcd(j, i);
      if (g*X == i*j) {
        printf(" %ld-%ld %ld-%ld\n", i, j, j, i);  // Промежуточная выдача
        k += 2;
      }
    }
  }
  printf("k=%ld\n", k);
  return 0;
}

Несколько странной мне показалась функция gcd08, я ее заменил. И как будто здесь ни при чем определение простоты числа...

не проходит по времени на 0.078 секунды

@New man · 28.01.2018, 02:42

Два вложенных цикла — это O(X^2).
Тебе надо снизить сложность алгоритма.

Предлагаю следующий алгоритм:
1) получить все простые числа от 0 до x. Сложность этого либо O(1), если мы можем заранее просчитать это для любых x,
O(x)< T(X) < O(x^2), если воспользуешься тем, что я скинул в посте, либо T(sqrt(x)) <= O(x), если оптимизируешь это под задачу (там можно это сделать).
2) Получить число простых сомножителей и подсчитать число разделений такого числа элементов на две группы. Первое делается быстрее O(x), второе я не знаю, как сделать, но уверен, что там сложность будет сильно ниже O(x).

Итого будет что-то около O(x), что пройдёт тесты.

Есть ещё проблема того, что может быть несколько одинаковых простых сомножителей. Предлагаю решить эту проблему тебе.

Можешь скинуть сслылку на задачку? Хочу попробовать решить на досуге.

Кликните здесь для просмотра всего текста

ЭТО НЕ РЕШЕНИЕ.
Но приблизительный порядок твоих действий.

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
// Example program
#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
#include <utility>
 
using namespace std;
using set = unordered_set;
// Глобальные переменные зло, конечно.
vector<unsigned> primes;
 
//Только для предпосчёта
inline bool is_prime_for_calc(const unsigned arg)
{
    auto it = primes.cbegin()
    while(it!=primes.end() && *it**it<arg)
    {
         ++it
    }
    if (it!=primes.end())
    {
        if (*it**it==arg)
            return false;
        else{
            primes.push_back(arg);
        }
    }
    else{
        primes.push_back(arg);
    }
    return true;
}
 
// Предпосчёт
set<unsigned> prime_set;
void init_primes(const unsigned max)
{
    primes.push_back(2);
    for (unsigned i = 3; i<=max; i+=2)
    {
        is_prime_for_calc(i);
    }
    prime_set = set<unsigned>(primes.begin(), primes.end());
}
 
// Работает только после предпосчёта
inline bool is_prime(unsigned arg)
{
    return prime_set.find(arg)!=prime_set.end();
}
 
unsigned prime_dividers(const unsigned arg)
{
    if (is_prime(arg))
        return {arg};
    unsigned r = 0;
    unsigned iter = arg;
    auto it = primes.cbegin()
    while(iter && it!=primes.cend())
    {
        while(it!=primes.cend() && iter%*it)
            ++it;
        if (it!=primes.cend())
        {
            const unsigned div = *it;
            while(!(iter% div))
            {
                r++;
            }
        }
    }
    return r;
}
 
unsigned get_two_dividers(prime_divs_count)
{
    return vector<pair<unsigned, unsigned>>(); // Вот тут мне лень думать уже
}
 
int main()
{
    unsigned X;
    cin>>X;
  init_primes(X);
  unsigned prime_divs = prime_dividers(X);
  cout<< get_two_dividers(prime_divs));
}

Добавлено через 39 минут
Хм, ступил, тут наименьшее общее кратное.

@_Milk_ · 28.01.2018, 12:57 **[ТС]**

Сообщение от New man

Два вложенных цикла — это O(X^2).
Тебе надо снизить сложность алгоритма.

Предлагаю следующий алгоритм:
1) получить все простые числа от 0 до x. Сложность этого либо O(1), если мы можем заранее просчитать это для любых x,
O(x)< T(X) < O(x^2), если воспользуешься тем, что я скинул в посте, либо T(sqrt(x)) <= O(x), если оптимизируешь это под задачу (там можно это сделать).
2) Получить число простых сомножителей и подсчитать число разделений такого числа элементов на две группы. Первое делается быстрее O(x), второе я не знаю, как сделать, но уверен, что там сложность будет сильно ниже O(x).

Итого будет что-то около O(x), что пройдёт тесты.

Есть ещё проблема того, что может быть несколько одинаковых простых сомножителей. Предлагаю решить эту проблему тебе.

Можешь скинуть сслылку на задачку? Хочу попробовать решить на досуге.

Кликните здесь для просмотра всего текста

ЭТО НЕ РЕШЕНИЕ.
Но приблизительный порядок твоих действий.

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
// Example program
#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
#include <utility>
 
using namespace std;
using set = unordered_set;
// Глобальные переменные зло, конечно.
vector<unsigned> primes;
 
//Только для предпосчёта
inline bool is_prime_for_calc(const unsigned arg)
{
    auto it = primes.cbegin()
    while(it!=primes.end() && *it**it<arg)
    {
         ++it
    }
    if (it!=primes.end())
    {
        if (*it**it==arg)
            return false;
        else{
            primes.push_back(arg);
        }
    }
    else{
        primes.push_back(arg);
    }
    return true;
}
 
// Предпосчёт
set<unsigned> prime_set;
void init_primes(const unsigned max)
{
    primes.push_back(2);
    for (unsigned i = 3; i<=max; i+=2)
    {
        is_prime_for_calc(i);
    }
    prime_set = set<unsigned>(primes.begin(), primes.end());
}
 
// Работает только после предпосчёта
inline bool is_prime(unsigned arg)
{
    return prime_set.find(arg)!=prime_set.end();
}
 
unsigned prime_dividers(const unsigned arg)
{
    if (is_prime(arg))
        return {arg};
    unsigned r = 0;
    unsigned iter = arg;
    auto it = primes.cbegin()
    while(iter && it!=primes.cend())
    {
        while(it!=primes.cend() && iter%*it)
            ++it;
        if (it!=primes.cend())
        {
            const unsigned div = *it;
            while(!(iter% div))
            {
                r++;
            }
        }
    }
    return r;
}
 
unsigned get_two_dividers(prime_divs_count)
{
    return vector<pair<unsigned, unsigned>>(); // Вот тут мне лень думать уже
}
 
int main()
{
    unsigned X;
    cin>>X;
  init_primes(X);
  unsigned prime_divs = prime_dividers(X);
  cout<< get_two_dividers(prime_divs));
}

Добавлено через 39 минут
Хм, ступил, тут наименьшее общее кратное.

Сылка на задачу

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@_Milk_ 0 / 0 / 1 Регистрация: 16.01.2018 Сообщений: 75
	26.01.2018, 15:47 [ТС]
	Но например х=6 тогда i=1 j=6 and i=6 j=1 ето два разних решения 0