use std::cmp::max;
use std::fmt;
use std::ops::{Add, Div, Mul, Sub};

pub struct Number {
    radix: usize,
    digits: Vec<u8>,
}

impl Number {
    pub fn parse(snum: &str, radix: usize) -> Result<Number, &str> {
        let snum = snum.as_bytes();
        let mut digits = Vec::new();
        for i in (0..snum.len()).rev() {
            match Number::parse_digit(snum[i]) {
                Some(digit) => {
                    if digit as usize >= radix {
                        return Err("Аргумент не является числом");
                    } else {
                        digits.push(digit);
                    }
                }
                None => {
                    return Err("Аргумент не является числом");
                }
            }
        }
        return Ok(Number { radix, digits });
    }

    pub fn len(&self) -> usize {
        self.digits.len()
    }

    fn parse_digit(c: u8) -> Option<u8> {
        if c >= 'a' as u8 {
            Some(c - 'a' as u8 + 10_u8)
        } else if c >= '0' as u8 {
            Some(c - '0' as u8)
        } else {
            None
        }
    }

    fn fix_leading_zeros(mut self) -> Self {
        let mut leading = 0;
        for i in (1..self.digits.len()).rev() {
            if self.digits[i] == 0 {
                leading += 1;
            } else {
                break;
            }
        }
        for _ in 0..leading {
            self.digits.pop();
        }
        return self;
    }
}

impl fmt::Display for Number {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        for i in (0..self.digits.len()).rev() {
            let digit = if self.digits[i] > 9 {
                ('a' as u8 - 10 + self.digits[i]) as char
            } else {
                ('0' as u8 + self.digits[i]) as char
            };
            write!(f, "{}", digit)?;
        }

        if self.radix != 10 {
            write!(f, "_{}", self.radix)?;
        }
        return Ok(());
    }
}

impl Add for Number {
    type Output = Self;

    fn add(self, other: Self) -> Self::Output {
        let mut k = 0;
        let len = max(self.len(), other.len());
        let mut digits = Vec::new();
        for i in 0..len {
            let mut digit = 0;
            if i < self.len() {
                digit += self.digits[i] as usize;
            }
            if i < other.len() {
                digit += other.digits[i] as usize;
            }
            digit += k;
            let (div, rem) = (digit / self.radix, digit % self.radix);
            digit = rem;
            k = div;
            digits.push(digit as u8);
        }
        if k != 0 {
            digits.push(k as u8);
        }

        return Number {
            radix: self.radix,
            digits,
        };
    }
}

impl Sub for Number {
    type Output = Self;

    fn sub(self, other: Self) -> Self::Output {
        let len = max(self.len(), other.len());
        let mut digits = Vec::new();
        let mut k = 0;
        for i in 0..len {
            let q1 = if i < self.len() {
                self.digits[i] as i64
            } else {
                0_i64
            };
            let q2 = if i < other.len() {
                other.digits[i] as i64
            } else {
                0_i64
            };
            let b = self.radix as i64;
            let res = q1 - q2 + k;
            let digit = (res + b) % b;
            k = if res < 0 { -1 } else { 0 };
            digits.push(digit as u8);
        }
        if k != 0 {
            digits.push(k as u8);
        }

        return Number {
            radix: self.radix,
            digits,
        }
        .fix_leading_zeros();
    }
}

impl Mul for Number {
    type Output = Self;

    fn mul(self, other: Self) -> Self::Output {
        let n = self.len();
        let m = other.len();
        let mut digits = vec![0; n + m];

        for j in 0..m {
            let vj = other.digits[j];
            if vj == 0 {
                digits[n + j] = 0;
            } else {
                let mut k = 0;
                for i in 0..n {
                    let ui = self.digits[i];
                    let t = ui * vj + digits[i + j] + k;
                    digits[i + j] = t % self.radix as u8;
                    k = t / self.radix as u8;
                }
                digits[n + j] = k;
            }
        }
        return Number {
            radix: self.radix,
            digits,
        }
        .fix_leading_zeros();
    }
}

impl Div for Number {
    type Output = Self;

    fn div(self, other: Self) -> Self::Output {
        fn mul_digit(a: &Vec<u8>, b: u8, radix: u8) -> Vec<u8> {
            let mut c = vec![0; a.len() + 1];
            let mut carry = 0;
            for i in 0..a.len() {
                let dig = a[i] * b;
                c[i] = dig % radix + carry;
                carry = dig / radix;
            }
            *c.last_mut().unwrap() = carry;
            return c;
        }

        let n = other.len();
        let m = self.len() - n;
        let b = self.radix as u8;

        let v1 = other.digits[other.len() - 1];
        let d = self.radix as u8 / (v1 + 1);

        let mut u = mul_digit(&self.digits, d, self.radix as u8);
        let mut v = mul_digit(&other.digits, d, self.radix as u8);
        v.pop();

        // println!("{d} {u:?} {v:?}");

        let mut quo = Vec::new();
        for j in 0..=m {
            // println!("{:?}", u);
            let uj = u[u.len() - 1 - j];
            let v1 = v[v.len() - 1];
            let q = if uj == v1 {
                b - 1
            } else {
                let uj1 = u[u.len() - 1 - (j + 1)];
                let uj2 = u[u.len() - 1 - (j + 2)];
                let v2 = v[v.len() - 2];
                let mut qc = (uj * b + uj1) / v1;
                while v2 * qc > (uj * b + uj1 - qc * v1) * b + uj2 {
                    qc -= 1;
                }
                qc
            };
            // println!("{uj} {v1}");
            // println!("{q}");
            quo.push(q);
            let u_sub = &u[u.len() - 1 - (j + n)..=u.len() - 1 - j];
            let u_sub = Number {
                radix: self.radix,
                digits: Vec::from(u_sub),
            }
            .fix_leading_zeros();
            let qv = Number {
                radix: other.radix,
                digits: mul_digit(&v, q, other.radix as u8),
            }
            .fix_leading_zeros();
            let p = u_sub - qv;
            for i in 0..n + 1 {
                let idx = u.len() - 1 - (j + n - i);
                u[idx] = if i < p.len() { p.digits[i] } else { 0 };
            }
        }

        // println!("{:?}", quo);
        quo.reverse();
        return Number {
            radix: self.radix,
            digits: quo,
        }
        .fix_leading_zeros();
    }
}