Поиск целых корней кубического уравнения по заданным коэффициентам?

Question

[artur_agishev]

Помогите решить(поделится идеей решения) данной задачи
Не проходит 16 тест
Кубическое уравнение (Время: 1 сек. Память: 16 Мб Сложность: 56%) Напишите программу, которая будет искать все целые X, удовлетворяющие уравнению AX3 + BX2 + C*X + D = 0, где A, B, C, D – заданные целые коэффициенты.

Входные данные Во входном файле INPUT.TXT записаны четыре целых числа: A, B, C, D. Все числа по модулю не превышают 2×109.

Выходные данные В выходной файл OUTPUT.TXT выведите сначала количество различных корней этого уравнения в целых числах, а затем сами корни в возрастающем порядке. Если уравнение имеет бесконечно много корней, то следует вывести в выходной файл одно число -1 (минус один).

Задача на acmp ru под номером 257

Мой код: https://pastebin.com/ajaexiek

Я ищу делители числа d и по ним отбираю корни, так же я рассмотрел все случаи когда коэффициенты равен(равны) нулю

Код здесь:

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
vector <ll> s;
 
ll check(ll n, ll a, ll b, ll c, ll d){
    return (a*n*n*n+b*n*n+c*n+d);
}
 
void poisk(ll n, ll a, ll b, ll c, ll d){
    for (ll i = 1; i*i <= abs(n); i++){ 
        if (n % i == 0){                    
            if (check(i, a, b, c, d) == 0)
                s.push_back(i);
            if (check(n/i, a, b, c, d) == 0)
                s.push_back(n/i);
            if (check(-1*i, a, b, c, d) == 0)
                s.push_back(-1*i);
            if (check(-1*n/i, a, b, c, d) == 0)
                s.push_back(-1*n/i);
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll a, b, c, d; 
    cin >> a >> b >> c >> d;    
    if (a == 0 and b == 0 and c == 0 and d == 0){
        cout << -1;
        return 0;
    }
    if (a != 0 and b!=0 and c==0 and d==0 or a == 0 and b == 0 and c != 0 and d == 0 or a == 0 and b != 0 and c == 0 and d == 0 or a != 0 and b == 0 and c == 0 and d == 0 or a != 0 and b == 0 and c != 0 and d == 0 or a!= 0 and b!=0 and c!=0 and d==0)
        s.push_back(0);
    if (a == 0 and b != 0 and c != 0 and d == 0 or a != 0 and b == 0 and c != 0 and d == 0 or a!= 0 and b!=0 and c!=0 and d==0)
        poisk(c, a, b, c, d);
    if (a != 0 and b!=0 and c==0 and d==0)  
        poisk(b, a, b, c, d);   
    poisk(d, a, b, c, d);   
    sort(s.begin(), s.end());
    s.erase((unique(s.begin(), s.end())), s.end());
    cout << s.size();
    for (ll i = 0; i < s.size(); i++)
        cout << " " << s[i];
    return 0;
}

Comments

[Lynn «Кофеман»]

Мне лень читать код, но из чего следует что корни должны быть делителями числа D?
D это же произведение всех корней и если среди них есть нецелые, то про D я вот так с ходу затрудняюсь сказать что-то определённое

[artur_agishev]

Lynn «Кофеман», нам даны целые коэффициенты. Если мы перенесем d в другую часть уравнения и вынесем X за скобки, то получится что X делится на d

[Lynn «Кофеман»]

Действительно, что-то я затупил.

Answer 1

[Wataru]

Во-первых, для таких больших коэффициентов вы в long long не влезаете, если в лоб считать.

Можно проверить в 2 этапа. Подсчитать A=a*x+b, B=c*x+d. Потом проверить что A*x*x = -B. Но тут нужно заранее отсечь случаи, когда abs(A) > abs(B)/(x*x). Тогда переполнений не будет.

Во-вторых, как же сложно у вас разбор случаев идет. Я не могу разобраться, что там происходит. Там наверняка опечатка, но я даже читать не хочу. Перепишите, пожалуйста. Вам надо найти самый старший ненулевой коэффициент и перебирать его делители. Плюс добавить корень 0, если этот коэффициент не d. Это делается сильно проще так:

if (d != 0) {
  n = d;
} else {
  s.push_back(0);
  if (c != 0) {
    n = c;
  } else if (b != 0) {
   n = b;
  } else {
   n = a;
  }
}
if (n == 0) {cout << "-1"; return}

Comments

[artur_agishev]

СПАСИБО! Я СДАЛ ЭТУ ЧЕРТОВУ ЗАДАЧУ. ВСЕ ДЕЛО БЫЛО В ПЕРЕПОЛНЕНИИ. В оправдании скажу, что мне 16 лет и я недавно только начала изучать программирование. Спасибо! Удачи, Вам!

[Wataru]

artur_agishev, Совет на будущее, если в коде возникает такая мешанина из условий на десятки выражений, до стоит остановиться и подумать, как это упростить.

Answer 2

[Андрей Ежгуров]

Условия слишком переусложнённые. Можно же проще:

if (abs(a) + abs(b) + abs(c) + abs(d) == 0) {
  cout << -1;
  return 0;
}
if (d != 0) { poisk(d, a, b, c, d); } else { s.push_back(0); }
if (c != 0) { poisk(c, a, b, c, d); } 
if (b != 0) { poisk(b, a, b, c, d); } 
if (a != 0) { poisk(a, a, b, c, d); }

Да, будут лишние циклы, но ничего не пропустили и ничего не перепутали.

Comments

[Антон Жилин]

else if

[Андрей Ежгуров]

Антон Жилин, Нет, не else if, а именно if: чтобы перебрать все возможные варианты.
А дальше по исходному коду в вопросе идёт отбор уникальных значений, так что дублей не будет.