#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

int hensel(int p, int j, vector<int> deri, vector<int> red, int exp, int n, int er){
int t=0, fpri=0, ll=0, zz=0;
long double yy=0;
double qw, pff, ptt, fprit;
if (exp<10){
     er=0;
     for (int q=0; q<n; q++){
        fprit = deri[q]*pow(j, (n-q));
}
    fpri = fprit;
    if (fpri%p==0){
        cout<<"ERROR"<<endl;
        er = 1;
    }
    for (int q=0; q<n+1; q++){
        yy = yy + red[q]*pow(j, (n-q));
    }
    for (int kk=0; kk<exp; kk++){
        yy = yy/p;
    }
    for (int t=0; t<p; t++){
        ptt = yy + t*fprit;
        zz = ptt;
    if (zz%p==0){
        cout<<t<<"*"<<p<<"^"<<exp<<" + ";
        qw = t;
        break;
    }
    }
    pff = j + qw*(pow(p,exp));
    j = pff;
    exp++;
    ll = pow(p,exp);
    j = j%ll;
    if(er==1){
        return 0;
    }
    else{
        return hensel(p, j, deri, red, exp, n, er);
    }
}
else{
    return p;
}
}


int main(){
    int n, y, p, zz, exp=1, i=0, er;
    double xx, yy, ee;
    vector <int> coef;
    vector <int> red;
    vector <int> deri;
    cout<<"Introduce the degree of the polynomial: ";
    cin>>n;
    cout<<"Introduce the coefficients in order: "<<endl;
    for (int e=0; e<n+1; e++){
        cin>>y;
        coef.push_back(y);
    }
    int a=2, b=3, z=0;
    vector <int> pr;
    pr.push_back(2);
    while (b<30){
        for (a=2; a*a<=b; a++){
            if (b%a==0){
            z=1;
            break;
    }
    }
        if (z==0){
            pr.push_back(b);

    }
       z=0;
       b = b+2;
    }
    for (int i=0; i<15; i++){
        for (int j=0; j<pr[i]; j++){
            red.clear();
            for (int w=0; w<n+1; w++){
                red.push_back(coef[w]%pr[i]);
            }
            ee=0;
            yy=0;
            for (int q=0; q<n+1; q++){
                ee = ee + red[q]*pow(j, (n-q));
            }
            int ss = ee;
            if (ss%pr[i]==0){
                p = pr[i];
                for (int ii=0; ii<n+1; ii++){
                deri.push_back((coef.size()-1-i)*coef[i]);
    }
    deri.pop_back();
    cout<<j<<" + ";
    cout<<hensel(p, j, deri, red, exp, n, er)<<endl;
    cout<<"MOD "<<pr[i]<<" x1 = "<<j<<endl<<endl;
            }
        }
    }
}