Система уравнений

@C0nstanta · Регистрация: 20.03.2022

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

Решал я на вид просую задачку, условие простое: пользователь вводит 2 числа P(1<=P<=10⁹), Q(1<=Q<=10¹⁸), имеется система уравнений x+y+z=P и x*y*z=Q, нужно найти минимальный x,y,z, если таких нет вывести -1. Загвостка заключается в том, что в 14 из 18 тестов числа больше миллиарада и тут уже давит time limit... Вот пример моего кода

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
#include <iostream>
using namespace std;
 
int main(){
    setlocale(LC_ALL, "Russian");
    int P, Q;
    cin>>P>>Q;
    int *del = new int;
    int n = 0;
    for(int i = 1; i<Q; i++){  //находим делители числа
        if(Q%i == 0){
            del[n] = i;
            n++;
        }
    }
    n++;
    int Y = 1;
    for(int i = 0; i<n and Y == 1; i++){
        for(int j = 0; j<n and Y == 1; j++){
            for(int k = 0; k<n and Y == 1; k++){
                int x = del[i];
                int y = del[j];
                int z = del[k];
                if(x+y+z == P and x*y*z == Q){
                    cout<<x<<" "<<y<<" "<<z<<endl;
                    Y=0;
                }
            }
        }
    }
    if(Y == 1)
        cout<<-1;
}

и вот еще пару тестиков(input:output)
7 8: 1 2 4
26 288: 2 12 12
1942743 221897492810000821: 352897 739117 850729
10440084 479525667212164032:58286 864432 9517366

@zss · 19.04.2023, 19:36

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

int *del = new int;

Как это вообще может работать?
память выделена под ОДНО число, т.е. есть только элемент del[0].

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
#include <iostream>
using namespace std;
 
int main(){
    setlocale(LC_ALL, "Russian");
    long long P, Q;
    cin>>P>>Q;
    cin.get();
    int n = 0;
    for(long long i = 1; i*i<Q; i++)
    {  //находим к-во делителей числа
        if(Q%i == 0)
            n++;
    }
    long long* del=new long long[n+1];
    n=0;
    for(long long i = 1; i*i<Q; i++)
    {  //находим делители числа
        if(Q%i == 0)
            del[n++]=i;
    }
    del[n++]=Q;
    bool Y = true;
    for(int i = 0; i<n && Y ; i++){
        long long x = del[i];
        for(int j = i; j<n && Y; j++){ //  !!   j=i
            long long y = del[j];
            for(int k = j; k<n && Y; k++){ // !!!  k=j
                long long z = del[k];
                if(x+y+z == P && x*y*z == Q){
                    cout<<x<<" "<<y<<" "<<z<<endl;
                    Y=false;
                }
            }
        }
    }
    if(Y)
        cout<<"-1";
    delete[] del;
    cin.get();
    return 0;
}

На моём компьютере релиз W32 последний вариант

10440084 479525667212164032:58286 864432 9517366

считает порядка 30 секунд.

@gunslinger · 19.04.2023, 22:04

А если использовать не тройной цикл, а двойной?
Ниже сырой набросок без приведенных выше оптимизаций. Но идея должна быть понятна.

Вспомогательные функции:

C++
1
2
3
4
5
6
7
8
9
unsigned long long func_x (unsigned long long y, unsigned long long z, unsigned long long P)
{
  return P - y - z;
}
//---------------------------------------------------------------------------
unsigned long long func_Q (unsigned long long y, unsigned long long z, unsigned long long P)
{
  return func_x(y, z, P) * y * z;
}

Основной код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
  unsigned long long i, j, x, y, z, P = 7, Q = 8;
  int status = -1;
  for (j = 1; j <= Q; j++)
    for (i = j; i <= Q / j; i++)
      if (func_Q(i, j, P) == Q)
      {
        y = i, z = j, x = func_x(y, z, P);
        i = Q + 1, j = Q + 1;
        status = 1;
      }
 
  // выводим результат
  String result = (status == 1) ? String(x) + "  " + String(y) + "  " + String(z) : String("-1");

@C0nstanta · 20.04.2023, 12:57 **[ТС]**

gunslinger, не много не пойму что не так с динамическим массивом. Но к сожалению ваше решение мне не очень подходит из-за времени, там ограничение около 2 секунд вроде

Добавлено через 6 минут
немного не пойму. Mожете выслать полный код?

@zss · 20.04.2023, 12:57

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

что не так с динамическим массивом

Память выделять нужно так, чтобы все элементы поместились, а не только один.

Кстати, действительно, 3-й цикл лишний, т.к. z=Q/(xy) (или z=P-x-y)

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
#include <iostream>
using namespace std;
 
int main(){
    setlocale(LC_ALL, "Russian");
    long long P, Q,x,y,z;
    cin>>P>>Q;
    cin.get();
    int n = 0;
    for(long long i = 1; i*i<Q; i++)
    {  
        if(Q%i == 0)
            n++;
    }
    long long* del=new long long[n+1];
    n=0;
    for(long long i = 1; i*i<Q; i++)
    {  
        if(Q%i == 0)
            del[n++]=i;
    }
    del[n++]=Q;
    bool NotFound = true;
    for(int i = 0; i<n && NotFound ; i++)
    {
        x = del[i];
        for(int j = i; j<n; j++)
        {
            y = del[j];
            z = Q/(x*y);
            if(x*y*z == Q && x+y+z == P)
            {
                NotFound=false;break;
            }
        }
    }
    if(NotFound)
        cout<<"-1";
    else
        cout<<x<<" "<<y<<" "<<z<<endl;
    delete[] del;
    cin.get();
    return 0;
}

Время уменьшается раза в два.

@C0nstanta · 20.04.2023, 13:43 **[ТС]**

zss, в общем... я не знаю что не так, но теперь же ваш код выводит нужный ответ за 0,09 секунд и проходит 7 тестов, но все же по остальным таймаут, я попробовал удалить последний цикл заменив его на z=P-x-y, но все же еще нужно оптимизировать

Алексей1153 · 20.04.2023, 14:18

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

for(long long i = 1; i*i<Q; i++)
{
if(Q%i == 0)
n++;
}

можно i*i<Q заменить на сравнение i с заранее посчитанным корнем из Q

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

for(long long i = 1; i*i<Q; i++)
{
if(Q%i == 0)
del[n++]=i;
}

тут то же самое

а также

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

if(Q%i == 0)
n++;

- тут избавиться от if

Добавлено через 10 минут
итог (нужно протестировать):

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
#include <iostream>
#include <cmath>
using namespace std;
 
int main(){
    setlocale(LC_ALL, "Russian");
    long long P, Q,x,y,z;
    cin>>P>>Q;
    cin.get();
    int n = 0;
    
    const double sqrtQ=std::sqrt(Q);
    for(long long i = 1; i<sqrtQ; i++)
    {  
        //if(Q%i == 0)n++;
        n+=!(Q%i);
    }
    long long* del=new long long[n+1];
    n=0;
    for(long long i = 1; i<sqrtQ; i++)
    {  
        if(Q%i == 0)
            del[n++]=i;
    }
    del[n++]=Q;
    bool NotFound = true;
    for(int i = 0; i<n && NotFound ; i++)
    {
        x = del[i];
        for(int j = i; j<n; j++)
        {
            y = del[j];
            z = Q/(x*y);
            if(x*y*z == Q && x+y+z == P)
            {
                NotFound=false;break;
            }
        }
    }
    if(NotFound)
        cout<<"-1";
    else
        cout<<x<<" "<<y<<" "<<z<<endl;
    delete[] del;
    cin.get();
    return 0;
}

@zss · 20.04.2023, 14:20

Движемся дальше.
Если задано x, то для нахождения y и z достаточно решить систему из 2 уравнений
z+y=P-x
z*y=Q/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
#include <iostream>
#include <math.h>
using namespace std;
typedef unsigned long long LL;
int main(){
    setlocale(LC_ALL, "Russian");
    LL P, Q,x,y,z;
    cin>>P>>Q;
    cin.get();
    int n = 0;
    for(LL i = 1; i*i<Q; i++)
    {  
        if(Q%i == 0)
            n++;
    }
    LL* del=new LL[n+1];
    n=0;
    for(LL i = 1; i*i<Q; i++)
    {  
        if(Q%i == 0)
            del[n++]=i;
    }
    del[n++]=Q;
    bool NotFound = true;
    for(int i = 0; i < n; i++)
    {
        x = del[i];
        LL P2=P-x;
        LL Q2=Q/x;
        y=P2/2-(LL)sqrt(P2*P2/4.-Q2);
        z=P2-y;
        if(x*y*z == Q)
        {
            NotFound=false;
            break;
        }
    }
    if(NotFound)
        cout<<"-1";
    else
        cout<<x<<" "<<y<<" "<<z<<endl;
    delete[] del;
    cin.get();
    return 0;
}

неприятным моментом здесь будет sqrt(P2*P2/4.-Q2)
т.к. он выполняется в плавающей арифметике.
Надо как-то избавиться от него.

@SpBerkut · 20.04.2023, 14:59

Попробуйте. А вдруг.

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
#include <iostream>
#include <cmath>
 
long long gcd(long long a, long long b){
    if(b==0) return a;
    return gcd(b, a%b);
}
 
long long secret(const long long P, const long long Q, long long x) {
    long long f = P*P*x - 2*P*x*x + x*x*x - 4*Q;
    long long g = gcd(f, x);
    f /= g;
    x /= g;
    if (g > 1)
        return (sqrt(x * f)) / (2*x);
    else
        return (sqrt(f) * sqrt(x) / (2*x*g));
}
 
int main()
{
    long long P;
    long long Q;
    std::cin >> P >> Q;
    bool find = false;
    for (long long x = 1; x < pow(Q, 1.0/3); x++) {
        if (Q % x) continue;
        long long s = (P - x)/2;
        long long sc = secret(P, Q, x);
        if ( Q / x == s*s - sc*sc ) {
            std::cout << x << '\t' << s - secret(P, Q, x) << '\t' << s + secret(P, Q, x);
            find = true;
            break;
        }
    }
    if (!find) std::cout << -1;
}

Добавлено через 35 минут
На всякого мудреца довольно простоты.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cmath>
 
int main()
{
    long long P, Q, x, y, z, Px, Qx, d;
    std::cin >> P >> Q;
    bool find = false;
    for (x = 1; x < pow(Q, 1.0/3); x++) {
        if (Q % x) continue;
        Px = P - x;
        Qx = Q / x;
        d = Px*Px - 4*Qx;
        y = (Px - sqrt(d))/2;
        z = (Px + sqrt(d))/2;
        if ( (Q == x*y*z) && (x+y+z == P) ) {
            std::cout << x << '\t' << y << '\t' << z;
            find = true;
            break;
        }
    }
    if (!find) std::cout << -1;
}

@C0nstanta · 20.04.2023, 16:40 **[ТС]**

Я фигею... Ведь точно знал что есть математическое решение. Можете пожалуйста +- объяснить принцип (я про второй код), код не проходит лишь один тест(input: output)
3000000 1000000000000000000:1000000 1000000 1000000

@SpBerkut · 20.04.2023, 16:48

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

код не проходит лишь один тест

А так?

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 <cmath>
 
struct pair {
    long long value = 0;
    unsigned power = 0;
}; 
 
int main()
{
    long long P, Q, x, y, z, Px, Qx, d;
    pair factors[60];
    unsigned magic[60] = {};
    std::cin >> P >> Q;
    unsigned count = 1-Q%2;
    long long N = Q;
    bool factorFound = false;
    while (N % 2 == 0) {
        if (!factorFound) {
            factorFound = true;
            factors[count-1].value = 2;
        }
        factors[count - 1].power++;
        N /= 2;
    }
    for (long long x = 3; x <= N; x+=2) {
        if (N % x) continue;
        count++;
        factorFound = false;
        while (N % x == 0) {
            if (!factorFound) {
                factorFound = true;
                factors[count-1].value = x;
            }
            factors[count - 1].power++;
            N /= x;
        }
    }
    
    magic[0] = 1;
    for (unsigned i = 1;  i < count; i++) {
        magic[i] = magic[i-1]*(factors[i-1].power+1);
    }
    
    unsigned t = 1;
    
    for (unsigned i = 0;  i < count; i++) {
        t *= factors[i].power+1;
    }
 
    bool find = false;
    for (unsigned i = 1; i <= t; i++) {
        x = 1;
        unsigned j = i;
        for (int k = count-1; k >= 0; k--) {
            x *= pow(factors[k].value, j / magic[k]);
            j %= magic[k];
        }
        
        Px = P - x;
        Qx = Q / x;
        d = Px*Px - 4*Qx;
        y = (Px - sqrt(d))/2;
        z = (Px + sqrt(d))/2;
        if ( (Q == x*y*z) && (x+y+z == P) ) {
            std::cout << x << '\t' << y << '\t' << z;
            find = true;
            break;
        }
    }
    if (!find) std::cout << -1;
}

@C0nstanta · 20.04.2023, 17:43 **[ТС]**

хах... так только все крашнулось, впринципе не так важно, код то рабочий

@SpBerkut · 21.04.2023, 09:52

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

Можете пожалуйста +- объяснить принцип (я про второй код)

Принцип следующий. Т.к. x*y*z = Q, значит min(x, y, z) не может превосходить значения в Q^(1/3).
Предположим, что x = min(x, y, z). Теперь переберём все возможные его значения от 1 до Q^(1/3). Т.к. Q <= 10^18, максимум придётся перебрать всего 1000000 значений.
Для конкретного x мы можем провернуть следующий фокус.

y*z = Q/x;
y+z = P-x;

Решим эту систему относительно переменных y и z. Для упрощения записи Qx = Q/x, Px = P - x;

z = Px - y;
y = Qx/z = Qx / (Px - y);

y * (Px - y) = Qx;
y*y - Px*y + Qx = 0;

Получили квадратное уравнение.

D = Px*Px - 4*Qx;

y = (-(-Px) - sqrt(D))/2.
z = (-(-Px) + sqrt(D))/2.

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

В моём последнем решении я не стал перебирать все значения x подряд. Сначала Q раскладываем на простые множители с их степенью.

Например число 479525667212164032 = 2^6 * 3^4 * 19 * 23 * 29 * 151 * 193 * 211 * 1187. Далее я перебираю все возможные наборы множителей. Общее количество вариантов определяется просто — к показателям степеней прибавляется единица и все числа перемножаются. Для числа, рассмотренного выше количество вариантов составит 4480. В 170 раз меньше, чем перебирать все варианты в лоб. Можно чуть улучшить и отсеивать наборы, произведение которых превышает Q^(1/3). Но и без этого получилось неплохо.

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

так только все крашнулось, впринципе не так важно

Требую подробностей.

Новые блоги и статьи Все статьи Все блоги /
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	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 Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии 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. . . .

@C0nstanta 0 / 0 / 0 Регистрация: 20.03.2022 Сообщений: 12
	20.04.2023, 12:57 [ТС]
	gunslinger, не много не пойму что не так с динамическим массивом. Но к сожалению ваше решение мне не очень подходит из-за времени, там ограничение около 2 секунд вроде Добавлено через 6 минут немного не пойму. Mожете выслать полный код? 0

@C0nstanta 0 / 0 / 0 Регистрация: 20.03.2022 Сообщений: 12
	20.04.2023, 13:43 [ТС]
	zss, в общем... я не знаю что не так, но теперь же ваш код выводит нужный ответ за 0,09 секунд и проходит 7 тестов, но все же по остальным таймаут, я попробовал удалить последний цикл заменив его на z=P-x-y, но все же еще нужно оптимизировать 0

@C0nstanta 0 / 0 / 0 Регистрация: 20.03.2022 Сообщений: 12
	20.04.2023, 16:40 [ТС]
	Я фигею... Ведь точно знал что есть математическое решение. Можете пожалуйста +- объяснить принцип (я про второй код), код не проходит лишь один тест(input: output) 3000000 1000000000000000000:1000000 1000000 1000000 0

@C0nstanta 0 / 0 / 0 Регистрация: 20.03.2022 Сообщений: 12
	20.04.2023, 17:43 [ТС]
	хах... так только все крашнулось, впринципе не так важно, код то рабочий 0

Система уравнений

Решение