let nom = "MARREC" and prenom = "Tristan";;

let pow m n =
  let rec rpow m n = match n with
    | 0 -> 1
    | _ -> (rpow m (n-1))*m
  in if n < 0 then failwith "l'exposant doit etre positif"
  else (rpow m n);;

let pgcd m n =
  let rec rpgcd m n =
    if m = 0 && n <> 0 then n
    else if n = 0 && m <> 0 then m
    else if m >= n && n > 0 then (rpgcd n (m mod n))
    else (rpgcd n m)
  in if n = 0 && m = 0 then failwith "truc"
  else (rpgcd m n);;

let ppcm m n = (m*n)/(pgcd m n);;

let replique l n = let rec rreplique l a n = match n with
    | 0 -> []
    | 1 -> l
    | _ -> (rreplique (l@a) a (n-1))
  in (rreplique l l n);;

let int_add l m n = let rec reverse = function
    | [] -> []
    | x::l -> (reverse l)@[x] in
  let rec add o p q = match (o,p,q) with
    | ([], [], r) -> (0, [r])
    | (a::[], b::[],r) -> ((a+b+r)/10,[(a+b+r) mod 10])
    | (a1::a2, b1::b2,r) -> let (ret,l) = (add a2 b2 ((a1+b1+r)/10))
        in (ret, ((a1+b1+r) mod 10)::l)
  in let (r,o) = (add (reverse l) (reverse m) n)
  in (r, reverse o) ;;


let etend_prefixe n (l1,l2) =
  let empty l = match l with
    | [] -> [0]
    | l -> l
  in let nl2 = (empty l2) in
  let rec ep n l = match (l, n) with
    | _, 0 -> []
    | (a::b), n -> [a]@(ep (n-1) b)
    | _, n -> match nl2 with
      | (a::b) -> [a]@(ep (n-1) nl2)
  in let first = l1@(ep n nl2)
  in let rec offset n l = match (l, n) with
      | l, 0 -> l
      | (a::b), _ -> (offset (n-1) b)
      | _, n -> (offset (n-1) nl2)
  in (offset n nl2);;

let mkInt l =
  let rec reverse = function
    | [] -> []
    | x::l -> (reverse l)@[x] in
  let pow m n =
    let rec rpow m n = match n with
      | 0 -> 1
      | _ -> (rpow m (n-1))*m
    in if n < 0 then failwith "l'exposant doit etre positif"
    else (rpow m n) in
  let rec rmkint l n =
    match (l,n) with
    | [], _ -> 0
    | (a::b), n -> (a*(pow 10 n))+(rmkint b (n+1))
  in (rmkint (reverse l) 0);;