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)
    | _::_, [], _ | [], _::_, _ -> failwith "ne devrais jamais arriver"
  in let (r,o) = (add (reverse l) (reverse m) n)
  in match (l,m,n) with
  | [], [], n -> (n, []);
  | _, _, _ -> (r, reverse o);;


let rec etend_prefixe n (l,m)= match (n,l,m) with
  | 0, _, _ -> (l,m)
  | n, _, [] -> (etend_prefixe (n-1) (l@[0],[0]))
  | n, _, a::b -> (etend_prefixe (n-1) (l@[a],b@[a]));;

let etend_pc lp lc (p,c) =
  let zero l = match l with
    | [] -> [0]
    | _ -> l in
  let rec size l = match l with
    | [] -> 0
    | _::b -> (size b)+1 in
  let (a,b) = etend_prefixe (lp-(size p)) (p,(zero c)) in
  let (d,e) = etend_prefixe (lc-(size (zero c))) (b,b) in
  (a,d);;

let radd t1 t2 = let zero t = match t with
    | a, [], b -> (a,[0],if b = [] then [0] else b)
    | a, d, b-> (a,d,if b = [] then [0] else b) in
  (zero t1), (zero t2);;

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

let rec mkQuot a b =
  let abs a = if a < 0 then a*(-1) else a in
  let p = (pgcd (abs a) (abs b)) in
  if b < 0 then (a/(p*(-1))), (b/(p*(-1)))
  else (a/p),(b/p);;

let addQuot a b = match (a,b) with
  | (a,b),(c,d) -> (mkQuot (a*d+b*c) (b*d));;

let rec couper l n = let rec first l n = match l with
    | [] -> []
    | (a::b) -> match a with
      | (c,d) -> if c = n
          then []
          else [a]@(first b n) in
  let rec second l n = match l with
    | [] -> []
    | (a::b) -> match a with
      | (c,d) -> if c = n
          then a::b
          else (second b n) in
  (first l n),(second l n);;