Finding integer roots of a cubic equation given coefficients?

Question

Mathematics

Help solve (share the idea of ​​solving) this problem
Cannot pass 16 test
Cubic equation (Time: 1 sec. Memory: 16 Mb Complexity: 56%) Write a program that will search for all integers X that satisfy the equation AX3 + BX2 + C*X + D = 0, where A, B, C, D are given integer coefficients.

Specifications Input The input file INPUT.TXT contains four integers: A, B, C, D. All modulo numbers do not exceed 2×109.

Output In the output file OUTPUT.TXT first output the number of different roots of this equation in integers, and then the roots themselves in ascending order. If the equation has infinitely many roots, then one number -1 (minus one) should be output to the output file.

Task on acmp ru number 257

My code:https://pastebin.com/ajaexiek

I'm looking for divisors of the number d and select the roots from them, I also considered all cases when the coefficients are (equal to) zero

The code is here:

#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;
}

Answer 1

Firstly, for such large coefficients, you don’t fit into long long if you count it head-on.
Can be checked in 2 steps. Calculate A=a*x+b, B=c*x+d. Then check that A*x*x = -B. But here it is necessary to cut off in advance the cases when abs(A) > abs(B)/(x*x). Then there will be no overflows.
Secondly, how difficult it is for you to analyze cases. I can't figure out what's going on there. It's probably a typo, but I don't even want to read it. Please rewrite. You need to find the oldest non-zero coefficient and iterate over its divisors. Plus add root 0 if this coefficient is not d. It's much easier like this:

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}

Answer 2

Conditions are too complicated. Could it be easier:

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); }

Yes, there will be extra cycles, but nothing was missed and nothing was mixed up.