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

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

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

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

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

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

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

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

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

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

C++

#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++

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++

#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++

#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++

#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++

#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++

// 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++

// 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_ 0 / 0 / 1 Регистрация: 16.01.2018 Сообщений: 75
	26.01.2018, 15:47 [ТС]	3
	Но например х=6 тогда i=1 j=6 and i=6 j=1 ето два разних решения 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	27.01.2018, 15:10	6
	Сообщение от _Milk_ по идее так? Да, похоже. Пробовали? Только вот еще одно замечание Ситуация i==j и при этом НОК(i, j) = x может возникнуть только в случае i == j == x 0

@_Milk_ 0 / 0 / 1 Регистрация: 16.01.2018 Сообщений: 75
	27.01.2018, 15:14 [ТС]	7
	Сообщение от Байт Да, похоже. Пробовали? Только вот еще одно замечание Ситуация i==j и при этом НОК(i, j) = x может возникнуть только в случае i == j == x К сожалению дает неправильный результат например я ввожу 6 должен быть результат 9 а выдает 18 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	27.01.2018, 16:19	8
	Сообщение от _Milk_ К сожалению дает неправильный результат К сожалению, в данный момент не могу заняться вашей задачей. Или подождите до вечера, или попробуйте пока сами. Там надо просто повнимательнее посмотреть арифметику... 1

@_Milk_ 0 / 0 / 1 Регистрация: 16.01.2018 Сообщений: 75
	27.01.2018, 16:32 [ТС]	9
	Сообщение от Байт К сожалению, в данный момент не могу заняться вашей задачей. Или подождите до вечера, или попробуйте пока сами. Там надо просто повнимательнее посмотреть арифметику... окей Добавлено через 2 минуты Если можете посмотреть буду очень благодарен 0