// Math
module ck/mathck/math

import std/core/undivstd/core/undiv

pub fun divisible-countck/math/divisible-count: (n : int, d : int) -> exn int(nn: int: intstd/core/types/int: V, dd: int: intstd/core/types/int: V)result: -> exn int: exnstd/core/exn/exn: (E, V) -> V intstd/core/types/int: V
  inline fun looploop: (i : int) -> int(ii: int: intstd/core/types/int: V)result: -> total int: intstd/core/types/int: V
    if ii: int %std/core/int/(%): (int, int) -> int dd: int ==std/core/int/(==): (x : int, y : int) -> bool 0literal: int
dec  = 0
hex8 = 0x00
bit8 = 0b00000000 then
      looploop: (i : int) -> int((ii: int /std/core/int/(/): (x : int, y : int) -> int dd: int).pretend-decreasingstd/core/undiv/pretend-decreasing: (x : int) -> int) +std/core/int/(+): (x : int, y : int) -> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001
    else
      0literal: int
dec  = 0
hex8 = 0x00
bit8 = 0b00000000
  if dd: int.absstd/core/int/abs: (i : int) -> exn int <=std/core/int/(<=): (x : int, y : int) -> exn bool 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001 then
    "d must satisfy the condition abs(d) >= 2"literal: string
count= 40.throwstd/core/exn/throw: (message : string, info : ? exception-info) -> exn int
  else
    looploop: (i : int) -> exn int(nn: int)

pub fun floor-logck/math/floor-log: (n : int, base : int) -> exn int(nn: int: intstd/core/types/int: V, basebase: int: intstd/core/types/int: V)result: -> exn int: exnstd/core/exn/exn: (E, V) -> V intstd/core/types/int: V
  inline fun looploop: (i : int) -> int(ii: int: intstd/core/types/int: V)result: -> total int: intstd/core/types/int: V
    if ii: int <std/core/int/(<): (x : int, y : int) -> bool basebase: int then
      0literal: int
dec  = 0
hex8 = 0x00
bit8 = 0b00000000
    else
      looploop: (i : int) -> int((ii: int /std/core/int/(/): (x : int, y : int) -> int basebase: int).pretend-decreasingstd/core/undiv/pretend-decreasing: (x : int) -> int) +std/core/int/(+): (x : int, y : int) -> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001
  if basebase: int <=std/core/int/(<=): (x : int, y : int) -> exn bool 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001 then
    "base must be greater than or equal to 2"literal: string
count= 39.throwstd/core/exn/throw: (message : string, info : ? exception-info) -> exn int
  else
    looploop: (i : int) -> exn int(nn: int)

pub fun ceil-logck/math/ceil-log: (n : int, base : int) -> exn int(nn: int: intstd/core/types/int: V, basebase: int: intstd/core/types/int: V)result: -> exn int: exnstd/core/exn/exn: (E, V) -> V intstd/core/types/int: V
  inline fun looploop: (i : int) -> int(ii: int: intstd/core/types/int: V)result: -> total int: intstd/core/types/int: V
    if ii: int <=std/core/int/(<=): (x : int, y : int) -> bool 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001 then
      0literal: int
dec  = 0
hex8 = 0x00
bit8 = 0b00000000
    else
      looploop: (i : int) -> int(((ii: int +std/core/int/(+): (x : int, y : int) -> int basebase: int -std/core/int/(-): (x : int, y : int) -> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001) /std/core/int/(/): (x : int, y : int) -> int basebase: int).pretend-decreasingstd/core/undiv/pretend-decreasing: (x : int) -> int) +std/core/int/(+): (x : int, y : int) -> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001
  if basebase: int <=std/core/int/(<=): (x : int, y : int) -> exn bool 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001 then
    "base must be greater than or equal to 2"literal: string
count= 39.throwstd/core/exn/throw: (message : string, info : ? exception-info) -> exn int
  else
    looploop: (i : int) -> exn int(nn: int)

// References:
// - <https://rsk0315.hatenablog.com/entry/2020/12/13/231307>
// - <https://github.com/atcoder/ac-library>

// Assume that the first three parameters are nonnegative and the remaining one
// is positive.
fun floor-sum-intlck/math/floor-sum-intl: (n : int, a : int, b : int, d : int) -> int(nn: int: intstd/core/types/int: V, aa: int: intstd/core/types/int: V, bb: int: intstd/core/types/int: V, dd: int: intstd/core/types/int: V)result: -> total int
  if aa: int >=std/core/int/(>=): (x : int, y : int) -> bool dd: int then
    floor-sum-intlck/math/floor-sum-intl: (n : int, a : int, b : int, d : int) -> int(nn: int.pretend-decreasingstd/core/undiv/pretend-decreasing: (x : int) -> int, aa: int %std/core/int/(%): (int, int) -> int dd: int, bb: int, dd: int) +std/core/int/(+): (x : int, y : int) -> int aa: int /std/core/int/(/): (x : int, y : int) -> int dd: int *std/core/int/(*): (int, int) -> int (nn: int *std/core/int/(*): (int, int) -> int (nn: int -std/core/int/(-): (x : int, y : int) -> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001) /std/core/int/(/): (x : int, y : int) -> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010)
  else if bb: int >=std/core/int/(>=): (x : int, y : int) -> bool dd: int then
    floor-sum-intlck/math/floor-sum-intl: (n : int, a : int, b : int, d : int) -> int(nn: int.pretend-decreasingstd/core/undiv/pretend-decreasing: (x : int) -> int, aa: int, bb: int %std/core/int/(%): (int, int) -> int dd: int, dd: int) +std/core/int/(+): (x : int, y : int) -> int bb: int /std/core/int/(/): (x : int, y : int) -> int dd: int *std/core/int/(*): (int, int) -> int nn: int
  else
    val n-maxn-max: int = aa: int *std/core/int/(*): (int, int) -> int (nn: int -std/core/int/(-): (x : int, y : int) -> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001) +std/core/int/(+): (x : int, y : int) -> int bb: int
    if n-maxn-max: int <std/core/int/(<): (x : int, y : int) -> bool dd: int then
      0literal: int
dec  = 0
hex8 = 0x00
bit8 = 0b00000000
    else
      val (std/core/types/Tuple2: forall<a,b> (fst : a, snd : b) -> (a, b)q-maxq-max: int, r-maxr-max: int)std/core/types/Tuple2: forall<a,b> (fst : a, snd : b) -> (a, b) = divmodstd/core/int/divmod: (x : int, y : int) -> (int, int)(n-maxn-max: int, dd: int)
      q-maxq-max: int +std/core/int/(+): (x : int, y : int) -> int floor-sum-intlck/math/floor-sum-intl: (n : int, a : int, b : int, d : int) -> int(q-maxq-max: int.pretend-decreasingstd/core/undiv/pretend-decreasing: (x : int) -> int, dd: int, r-maxr-max: int, aa: int)

// The sum of floor((ai + b) / d) for all i = 0, …, n - 1.
// Assume that `n >= 0` and `d != 0`.
pub fun floor-sumck/math/floor-sum: (n : int, a : int, b : int, d : int) -> int(nn: int: intstd/core/types/int: V, aa: int: intstd/core/types/int: V, bb: int: intstd/core/types/int: V, dd: int: intstd/core/types/int: V)result: -> total int
  if dd: int <std/core/int/(<): (x : int, y : int) -> bool 0literal: int
dec  = 0
hex8 = 0x00
bit8 = 0b00000000 then returnreturn: int floor-sumck/math/floor-sum: (n : int, a : int, b : int, d : int) -> int(nn: int.pretend-decreasingstd/core/undiv/pretend-decreasing: (x : int) -> int, ~std/core/int/(~): (i : int) -> intaa: int, ~std/core/int/(~): (i : int) -> intbb: int, ~std/core/int/(~): (i : int) -> intdd: int)std/core/types/Unit: ()
  assertstd/core/debug/assert: (message : string, condition : bool, @implicit/kk-file-line : string) -> ()
?kk-file-line=debug/file/kk-file-line(debug/file/kk-file,debug/file/kk-line)("n must be nonnegative"literal: string
count= 21, nn: int >=std/core/int/(>=): (x : int, y : int) -> bool 0literal: int
dec  = 0
hex8 = 0x00
bit8 = 0b00000000)
  assertstd/core/debug/assert: (message : string, condition : bool, @implicit/kk-file-line : string) -> ()
?kk-file-line=debug/file/kk-file-line(debug/file/kk-file,debug/file/kk-line)("d must not be zero"literal: string
count= 18, dd: int !=std/core/int/(!=): (x : int, y : int) -> bool 0literal: int
dec  = 0
hex8 = 0x00
bit8 = 0b00000000)
  val a'a': int = aa: int %std/core/int/(%): (int, int) -> int dd: int
  val b'b': int = bb: int %std/core/int/(%): (int, int) -> int dd: int
  (aa: int -std/core/int/(-): (x : int, y : int) -> int a'a': int) /std/core/int/(/): (x : int, y : int) -> int dd: int *std/core/int/(*): (int, int) -> int (nn: int *std/core/int/(*): (int, int) -> int (nn: int -std/core/int/(-): (x : int, y : int) -> int 1literal: int
dec  = 1
hex8 = 0x01
bit8 = 0b00000001) /std/core/int/(/): (x : int, y : int) -> int 2literal: int
dec  = 2
hex8 = 0x02
bit8 = 0b00000010)
    +std/core/int/(+): (x : int, y : int) -> int (bb: int -std/core/int/(-): (x : int, y : int) -> int b'b': int) /std/core/int/(/): (x : int, y : int) -> int dd: int *std/core/int/(*): (int, int) -> int nn: int
    +std/core/int/(+): (x : int, y : int) -> int floor-sum-intlck/math/floor-sum-intl: (n : int, a : int, b : int, d : int) -> int(nn: int, a'a': int, b'b': int, dd: int)