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


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


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 list n =
  let rec rreplique list list2 n = match n with
    | 0 -> []
    | 1 -> list
    | _ -> (rreplique (list@list2) list2 (n-1))
  in (rreplique list list n);;


let int_add list1 list2 n =
  let rec reverse = function
    | [] -> []
    | x::list1 -> (reverse list1)@[x] in
  let rec add add_list1 add_list2 q = match (add_list1, add_list2, q) with
    | ([], [], r) -> (0, [r])
    | (a::[], b::[], r) -> ((a+b+r)/10,[(a+b+r) mod 10])
    | (a1::a2, b1::b2, r) -> let (ret,list1) = (add a2 b2 ((a1+b1+r)/10))
        in (ret, ((a1+b1+r) mod 10)::list1)
    | _::_, [], _ | [], _::_, _ -> failwith "ne devrais jamais arriver"
  in let (r,add_list1) = (add (reverse list1) (reverse list2) n)
  in match (list1, list2, n) with
  | [], [], n -> (n, []);
  | _, _, _ -> (r, reverse add_list1);;


let rec etend_prefixe n (list1, list2)= match (n, list1, list2) with
  | 0, _, _ -> (list1, list2)
  | n, _, [] -> (etend_prefixe (n-1) (list1@[0], [0]))
  | n, _, deb::fin -> (etend_prefixe (n-1) (list1@[deb], fin@[deb]));;


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


let mkInt list =
  let rec reverse = function
    | [] -> []
    | deb::fin -> (reverse fin)@[deb] in
  let rec rec_mkint list n =
    match (list,n) with
    | [], _ -> 0
    | (a::b), n -> (a*(pow 10 n))+(rec_mkint b (n+1))
  in (rec_mkint (reverse list) 0);;


let rec mkQuot a b =
  let abs n = if n < 0 then n*(-1) else n 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 list n = let rec first list n = match list with
    | [] -> []
    | (a::b) -> match a with
      | (c,d) -> if c = n
          then []
          else [a]@(first b n) in
  let rec second list n = match list with
    | [] -> []
    | (a::b) -> match a with
      | (c,d) -> if c = n
          then a::b
          else (second b n) in
  (first list n),(second list n);;