Source

spoj-ocaml / 00017.CRYPTO1 / crypto1.ml

Full commit
(* https://www.spoj.pl/problems/CRYPTO1/ *)

open Num

let (|>) x y = y x


let p = num_of_string "4000000007"
let k = (p -/ (num_of_int 3)) // (num_of_int 4)

let limit = num_of_string "1924992000"

let zero = num_of_int 0
let one  = num_of_int 1


let expt_mod a n p =
  let rec em_aux accu a p n =
    if n == zero then accu
    else              em_aux (mod_num (accu */ a) p) a p (n -/ one)
  in em_aux one a p n

let solve enct =
  let q = expt_mod enct (k +/ one) p in
  if q </ limit then q
  else               p -/ q


let main () =
  let enct = Scanf.scanf "%s\n" (fun x -> x) |> num_of_string in
  let dect = solve enct in
  Printf.printf "%s\n" (string_of_num dect)

let () = main ()