type big_int == int list ;;

let add_big_int (s1:big_int) (s2:big_int) =
        let rec aux = fun
                | [] [] 0 -> []
                | [] [] r -> [r]
                | (a::p) [] 1 when a = 99999999 -> 0::(aux p [] 1)
                | (a::p) [] r -> (a+r)::p
                | [] (a::p) r -> aux (a::p) [] r
                | (a::p) (b::q) r -> let n = a+b+r in
                                     if n < 100000000 then n::(aux p q 0)
                                     else (n-100000000)::(aux p q 1)
        in
        ((aux s1 s2 0):big_int);
;;

exception A ;;

let sous_big_int (s1:big_int) (s2:big_int) =
        let rec aux = fun
                | [a] [b] r when a >= b+r -> [a-b-r]
                | (a::p) [] 1 when a = 0 -> 99999999::(aux p [] 1)
                | (a::p) [] r -> (a-r)::p
                | (a::p) (b::q) r -> let n = a-b-r in
                                     if n >= 0 then n::(aux p q 0)
                                     else (n+100000000)::(aux p q 1)
                | _ _ _ -> raise A
        in
        ((aux s1 s2 0):big_int);
;;

let rec mult_int s p =
        if p = 0 then [] else (
                let n = mult_int s (p/2) in
                let nn = add_big_int n n in
                if p mod 2 = 0 then nn else add_big_int nn s;
        );
;;

let rec mult_big_int s1 = fun
        | [] -> []
        | (a::q) -> let b = mult_int s1 a and c = mult_big_int s1 q in
                    add_big_int b (0::c)
;;

let rec karatsuba a b =
        let rec coupe = fun
                | l 0 -> [],l
                | (a::q) n -> let s,t = coupe q (n-1) in (a::s),t
                | _ _ -> failwith "coupe"
        in
        let rec make = fun
                | 0 -> []
                | n -> 0::(make (n-1))
        in
        let n = list_length b in
        if n = 1 then mult_int a (hd b) else (
                let a2,a1 = coupe a (n/2)
                and b2,b1 = coupe b (n/2) in
                let c1 = karatsuba a1 b1
                and c2 = karatsuba (add_big_int a1 a2) (add_big_int b1 b2)
                and c3 = karatsuba a2 b2 in
                let c2 = sous_big_int (sous_big_int c2 c1) c3 in
                add_big_int c3 (add_big_int ((make (n/2))@c2) ((make (n/2*2))@c1));
        );
;;

let mult_big_int (a:big_int) (b:big_int) =
        if list_length a > list_length b then (
                if list_length b >= 64 then karatsuba a b
                else mult_big_int a b;
        ) else (
                if list_length a >= 64 then karatsuba b a
                else mult_big_int b a;
        );
;;


let canonize s n =
        let l = string_length s in
        if l > n then failwith "liste trop longue";
        (make_string (n-l) `0` ) ^ s;
;;

let decanonize s =
        let n = string_length s and i = ref 0 in
        while !i < n && s.[!i] = `0` do incr i done;
        sub_string s !i (n - !i);
;;

let debfin s =
        let n = string_length s in
        (sub_string s 0 (n-8)), (sub_string s (n-8) 8);
;;

let string_of_big_int (b:big_int) =
        let rec aux = fun
                | [] -> ""
                | (a::q) -> (aux q)^(canonize (string_of_int a) 8)
        in
        decanonize (aux b);
;;

let rec big_int_of_string = fun
        | "" -> []
        | s when string_length s < 9 -> [int_of_string s]
        | s -> let d,f = debfin s in (int_of_string f)::((big_int_of_string d):big_int)
;;

let add a b =
 string_of_big_int (add_big_int (big_int_of_string a) (big_int_of_string b)) ;;

let sous a b =
 string_of_big_int (sous_big_int (big_int_of_string a) (big_int_of_string b)) ;;

let mult a b =
 string_of_big_int (mult_big_int (big_int_of_string a) (big_int_of_string b)) ;;

let inf a b =
        let l = string_length a and n = string_length b in
        l < n || (l = n && a < b);
;;
let inf a b = inf (decanonize a) (decanonize b) ;;

let ioe a b =
        let l = string_length a and n = string_length b in
        l < n || (l = n && a <= b);
;;
let ioe a b = ioe (decanonize a) (decanonize b) ;;


let div a b =

(* div1 : division par un petit entier *)

let rec div1 a n =
        let aa = ref a and q = ref "" in
        while string_length !aa > 8 do
                let aaa = int_of_string (sub_string !aa 0 8) in
                let l = (string_length !aa) - 8 in
                let ll = make_string l `0` in
                let qq = (string_of_int (aaa/n)) ^ ll
                and c = (string_of_int (aaa mod n)) ^ (sub_string !aa 8 l) in
                aa:= c;
                q:= add !q qq;
        done;
        let aaa = int_of_string !aa in
        q:= add !q (string_of_int (aaa/n));
        !q,(string_of_int (aaa mod n));
in

(* div2 : résultat obtenu chiffre par chiffre *)

let div2 a b =
        if inf a b then "",a else (
                let n = string_length a and m = string_length b in
                let aa = ref (sub_string a 0 (m-1)) and q = ref "" in
                for i=m-1 to n-1 do
                        aa:= !aa^(string_of_char a.[i]);
                        let c = ref 1 in
                        while ioe (mult b (string_of_int !c)) !aa do incr c done;
                        decr c;
                        let c = string_of_int !c in
                        q:= !q^c;
                        aa:= sous !aa (mult b c);
                done;
                !q,!aa;
        );
in

(* div3 : division 8 chiffres par 4 chiffres *)

let rec div3 a b =
        let n = string_length b
        and aa = ref a and q = ref "" and bb = int_of_string (sub_string b 0 4) + 1 in
        while (string_length !aa) - n > 3 do
                let aaa = int_of_string (sub_string !aa 0 8) in
                let qq = string_of_int (aaa/bb) in
                let c = mult b qq in
                let l = string_length !aa - string_length c in
                let l = if c <= !aa then l else l-1 in
                let ll = make_string l `0` in
                let c = c ^ ll and qq = qq ^ ll in
                aa:= sous !aa c;
                q:= add !q qq;
        done;
        let qq,r = div2 !aa b in
        q:= add !q qq;
        !q,r;
in

if b = "" then failwith "division par zéro";
if string_length b < 8 then div1 a (int_of_string b)
else div3 a b;
;;

let div a b =
        let q,r = div (decanonize a) (decanonize b) in
        q,decanonize r;
;;

let bi_quo a b = fst (div a b) ;;
let bi_mod a b = snd (div a b) ;;


(* longs entiers signés *)

let add0 = add ;;

let rec add a b =
        if a = "" then b else (if b = "" then a else (
        let n = string_length a and m = string_length b in
        match a.[0], b.[0] with
                | `-`, `-` -> "-" ^ (add0 (sub_string a 1 (n-1)) (sub_string b 1 (m-1)))
                | `-`, _ -> add b a
                | _, `-` -> let bb = sub_string b 1 (m-1) in
                            if ioe bb a then sous a bb else "-" ^ (sous bb a)
                | _, _ -> add0 a b
        ))
;;

let sous a b =
        if b = "" then a else (
        if b.[0] = `-` then add a (sub_string b 1 ((string_length b)-1))
        else add a ("-" ^ b));
;;

let mult a b =
        if a = "" || b = "" then "" else (
        let n = string_length a and m = string_length b in
        match a.[0], b.[0] with
                | `-`, `-` -> mult (sub_string a 1 (n-1)) (sub_string b 1 (m-1))
                | `-`, _ -> "-" ^ (mult (sub_string a 1 (n-1)) b)
                | _, `-` -> "-" ^ (mult a (sub_string b 1 (m-1)))
                | _, _ -> mult a b
        )
;;

let div a b =
        if b = "" then failwith "division par zéro" else (if a = "" then "","" else (
        let n = string_length a and m = string_length b in
        match a.[0], b.[0] with
                | `-`, `-` -> div (sub_string a 1 (n-1)) (sub_string b 1 (m-1))
                | `-`, _ -> let q,r = div (sub_string a 1 (n-1)) b in 
                            (if q = "" then "" else ("-" ^ q)),(if r = "" then "" else ("-" ^ r))
                | _, `-` -> let q,r = div a (sub_string b 1 (m-1)) in
                            (if q = "" then "" else ("-" ^ q)),(if r = "" then "" else ("-" ^ r))
                | _, _ -> div a b
        ))
;;

let bi_quo a b = fst (div a b) ;;
let bi_mod a b = snd (div a b) ;;


let decanonize s =
        if s = "" then "" else (
                if s.[0] = `-` then (
                        let s = decanonize (sub_string s 1 ((string_length s)-1)) in
                        if s = "" then "" else ("-" ^ s);
                ) else decanonize s;
        )
;;

let inf a b =
        if a = "" then (if b = "" then false else (if b.[0] = `-` then false else true)
        ) else (if b = "" then (if a.[0] = `-` then true else false) else (
        let n = string_length a and m = string_length b in
        match a.[0], b.[0] with
                | `-`, `-` -> inf (sub_string b 1 (m-1)) (sub_string a 1 (n-1))
                | `-`, _ -> true
                | _, `-` -> false
                | _, _ -> inf a b
        ))
;;
let inf a b = inf (decanonize a) (decanonize b) ;;

let ioe a b =
        if a = "" then (if b = "" then true else (if b.[0] = `-` then false else true)
        ) else (if b = "" then (if a.[0] = `-` then true else false) else (
        let n = string_length a and m = string_length b in
        match a.[0], b.[0] with
                | `-`, `-` -> ioe (sub_string b 1 (m-1)) (sub_string a 1 (n-1))
                | `-`, _ -> true
                | _, `-` -> false
                | _, _ -> ioe a b
        ))
;;
let ioe a b = ioe (decanonize a) (decanonize b) ;;


let rec puiss a n =
        if n=0 then "1" else (
                let b = puiss (mult a a) (n/2) in
                if n mod 2 = 0 then b else (mult a b)
        );
;;

let rec fact = fun
        | n when n < 2 -> "1"
        | n -> mult (fact (n-1)) (string_of_int n)
;;

let bi_incr i = i:= add !i "1" ;;