#1024043 (Fortran) No.2380 Sylow P-subgroup

• 問題: No.2380 Sylow P-subgroup
• ユーザー: osada-yum
• 提出日時: 2024-11-02 02:54:32
• 言語: Fortran (gFortran 14.2.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 10,510 bytes
• コンパイル時間: 921 ms
• コンパイル使用メモリ: 36,736 KB
• 実行使用メモリ: 6,820 KB
• 最終ジャッジ日時: 2024-11-02 02:54:35
• 合計ジャッジ時間: 2,215 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 14

ソースコード

!> This file was processed by `fypp`.
!> Today's fortune: "Bad WA", really OK?
!> ランダムウォーク猿「'Bellman-Ford' で はっぴー.」
!> ギャンブラー猿「流れが来てない...」
module modint_m
  use, intrinsic :: iso_fortran_env
  implicit none
  private
  integer(int64), parameter :: modulo = 998244353
  public :: modint
  public :: assignment(=), operator(+), operator(-), operator(*), operator(/), inv, operator(**), combination
  public :: min, max
  type :: modint
     integer(int64) :: val_
   contains
     procedure, pass :: to_i64 => to_i64_modint
  end type modint
  interface modint
     module procedure :: init_modint_i32, init_modint_i64
  end interface modint
  interface assignment(=)
     module procedure :: assign_m_from_m, assign_m_from_i32, assign_m_from_i64
  end interface assignment(=)
  interface operator(+)
     module procedure :: add_m_m, add_i32_m, add_i64_m, add_m_i32, add_m_i64
  end interface operator(+)
  interface operator(-)
     module procedure :: sub_m_m, sub_i32_m, sub_i64_m, sub_m_i32, sub_m_i64
  end interface operator(-)
  interface operator(*)
     module procedure :: mul_m_m, mul_i32_m, mul_i64_m, mul_m_i32, mul_m_i64
  end interface operator(*)
  interface inv
     module procedure :: inv_modint, inv_i32, inv_i64
  end interface inv
  interface operator(/)
     module procedure :: div_m_m, div_i32_m, div_i64_m, div_m_i32, div_m_i64
  end interface operator(/)
  interface operator(**)
     module procedure :: pow_m_i32, pow_m_i64
  end interface operator(**)
  interface combination
     module procedure :: combination_m_m, combination_m_i32, combination_m_i64, combination_i32_m, combination_i64_m
  end interface combination
  interface min
     module procedure :: min_m
  end interface min
  interface max
     module procedure :: max_m
  end interface max
contains
  pure integer(int64) function to_i64_modint(mx) result(res)
    class(modint), intent(in) :: mx
    res = mx%val_
  end function to_i64_modint
  pure elemental type(modint) function init_modint_i32(x) result(res)
    integer(int32), intent(in) :: x
    res = modint(int(x, int64))
  end function init_modint_i32
  pure elemental type(modint) function init_modint_i64(x) result(res)
    integer(int64), intent(in) :: x
    res%val_ = mod(x, modulo)
    if (res%val_ < 0) res%val_ = res%val_ + modulo
  end function init_modint_i64
  pure subroutine assign_m_from_m(this, x)
    type(modint), intent(out) :: this
    type(modint), intent(in) :: x
    this%val_ = x%val_
  end subroutine assign_m_from_m
  pure subroutine assign_m_from_i32(this, x)
    type(modint), intent(out) :: this
    integer(int32), intent(in) :: x
    this = modint(x)
  end subroutine assign_m_from_i32
  pure subroutine assign_m_from_i64(this, x)
    type(modint), intent(out) :: this
    integer(int64), intent(in) :: x
    this = modint(x)
  end subroutine assign_m_from_i64
  pure type(modint) function add_m_m(mx, my) result(res)
    type(modint), intent(in) :: mx, my
    res%val_ = mod(mx%val_ + my%val_, modulo)
  end function add_m_m
  pure type(modint) function add_i32_m(x, my) result(res)
    integer(int32), intent(in) :: x
    type(modint), intent(in) :: my
    res = int(x, int64) + my
  end function add_i32_m
  pure type(modint) function add_i64_m(x, my) result(res)
    integer(int64), intent(in) :: x
    type(modint), intent(in) :: my
    res = modint(x) + my
  end function add_i64_m
  pure type(modint) function add_m_i32(mx, y) result(res)
    type(modint), intent(in) :: mx
    integer(int32), intent(in) :: y
    res = mx + modint(y)
  end function add_m_i32
  pure type(modint) function add_m_i64(mx, y) result(res)
    type(modint), intent(in) :: mx
    integer(int64), intent(in) :: y
    res = mx + modint(y)
  end function add_m_i64
  pure type(modint) function sub_m_m(mx, my) result(res)
    type(modint), intent(in) :: mx, my
    res%val_ = mod(mx%val_ - my%val_, modulo)
    if (res%val_ < 0) res%val_ = res%val_ + modulo
  end function sub_m_m
  pure type(modint) function sub_i32_m(x, my) result(res)
    integer(int32), intent(in) :: x
    type(modint), intent(in) :: my
    res = modint(x) - my
  end function sub_i32_m
  pure type(modint) function sub_i64_m(x, my) result(res)
    integer(int64), intent(in) :: x
    type(modint), intent(in) :: my
    res = modint(x) - my
  end function sub_i64_m
  pure type(modint) function sub_m_i32(mx, y) result(res)
    type(modint), intent(in) :: mx
    integer(int32), intent(in) :: y
    res = mx - modint(y)
  end function sub_m_i32
  pure type(modint) function sub_m_i64(mx, y) result(res)
    type(modint), intent(in) :: mx
    integer(int64), intent(in) :: y
    res = mx - modint(y)
  end function sub_m_i64
  pure type(modint) function mul_m_m(mx, my) result(res)
    type(modint), intent(in) :: mx, my
    res%val_ = mod(mx%val_ * my%val_, modulo)
  end function mul_m_m
  pure type(modint) function mul_i32_m(x, my) result(res)
    integer(int32), intent(in) :: x
    type(modint), intent(in) :: my
    res = modint(x) * my
  end function mul_i32_m
  pure type(modint) function mul_i64_m(x, my) result(res)
    integer(int64), intent(in) :: x
    type(modint), intent(in) :: my
    res = modint(x) * my
  end function mul_i64_m
  pure type(modint) function mul_m_i32(mx, y) result(res)
    type(modint), intent(in) :: mx
    integer(int32), intent(in) :: y
    res = mx * modint(y)
  end function mul_m_i32
  pure type(modint) function mul_m_i64(mx, y) result(res)
    type(modint), intent(in) :: mx
    integer(int64), intent(in) :: y
    res = mx * modint(y)
  end function mul_m_i64

  pure type(modint) function inv_modint(mx) result(res)
    type(modint), intent(in) :: mx
    integer(int64) :: g, a_inv, y
    call extend_euclid(mx%val_, modulo, g, a_inv, y)
    !> if (g /= 1) error stop 1, something wrong...
    !> g == 1.
    res = modint(a_inv)
  end function inv_modint
  pure type(modint) function inv_i32(x) result(res)
    integer(int32), intent(in) :: x
    res = inv_modint(modint(x))
  end function inv_i32
  pure type(modint) function inv_i64(x) result(res)
    integer(int64), intent(in) :: x
    res = inv_modint(modint(x))
  end function inv_i64
  !> a*x + b*y == g
  pure subroutine extend_euclid(a, b, g, x, y)
    integer(int64), intent(in)  :: a, b
    integer(int64), intent(out) :: g, x, y
    integer(int64) :: q
    integer(int64) :: zs(0:1), xs(0:1), ys(0:1)
    integer(int32) :: old, next
    zs(0) = a; zs(1) = b
    xs(0) = 1; xs(1) = 0
    ys(0) = 0; ys(1) = 1
    old = 1
    do
       next = ieor(old, 1)
       if (zs(old) == 0) exit
       q = zs(next) / zs(old)
       zs(next) = zs(next) - q*zs(old)
       xs(next) = xs(next) - q*xs(old)
       ys(next) = ys(next) - q*ys(old)
       old = next
    end do
    x = xs(next)
    y = ys(next)
    g = a*x + b*y
  end subroutine extend_euclid

  pure type(modint) function div_m_m(mx, my) result(res)
    type(modint), intent(in) :: mx, my
    res = mx * inv(my)
  end function div_m_m
  pure type(modint) function div_i32_m(x, my) result(res)
    integer(int32), intent(in) :: x
    type(modint), intent(in) :: my
    res = modint(x) / my
  end function div_i32_m
  pure type(modint) function div_i64_m(x, my) result(res)
    integer(int64), intent(in) :: x
    type(modint), intent(in) :: my
    res = modint(x) / my
  end function div_i64_m
  pure type(modint) function div_m_i32(mx, y) result(res)
    type(modint), intent(in) :: mx
    integer(int32), intent(in) :: y
    res = mx / modint(y)
  end function div_m_i32
  pure type(modint) function div_m_i64(mx, y) result(res)
    type(modint), intent(in) :: mx
    integer(int64), intent(in) :: y
    res = mx / modint(y)
  end function div_m_i64

  pure type(modint) function pow_m_i32(mx, p) result(res)
    type(modint), intent(in) :: mx
    integer(int32), intent(in) :: p
    res = mx ** int(p, int64)
  end function pow_m_i32
  pure type(modint) function pow_m_i64(mx, p) result(res)
    type(modint), intent(in) :: mx
    integer(int64), intent(in) :: p
    type(modint) :: mv, mx_powered
    integer(int64) :: pow
    mv = 1
    mx_powered = mx
    pow = p
    do while (pow /= 0)
       if (iand(pow, b'1') == 1) then
          mv = mv * mx_powered
       end if
       mx_powered = mx_powered * mx_powered
       pow = ishft(pow, -1)
    end do
    res = mv
  end function pow_m_i64
  pure type(modint) function combination_m_m(mn, mr) result(res)
    type(modint), intent(in) :: mn, mr
    integer(int64) :: i
    res = modint(1)
    do i = 1, mr%to_i64()
       res = (res * (mn%to_i64() - i + 1)) / i
    end do
  end function combination_m_m
  pure type(modint) function combination_m_i32(mn, r) result(res)
    type(modint), intent(in) :: mn
    integer(int32), intent(in) :: r
    res = combination(mn, modint(r))
  end function combination_m_i32
  pure type(modint) function combination_m_i64(mn, r) result(res)
    type(modint), intent(in) :: mn
    integer(int64), intent(in) :: r
    res = combination(mn, modint(r))
  end function combination_m_i64
  pure type(modint) function combination_i32_m(n, mr) result(res)
    integer(int32), intent(in) :: n
    type(modint), intent(in) :: mr
    res = combination(modint(n), mr)
  end function combination_i32_m
  pure type(modint) function combination_i64_m(n, mr) result(res)
    integer(int64), intent(in) :: n
    type(modint), intent(in) :: mr
    res = combination(modint(n), mr)
  end function combination_i64_m
  pure type(modint) function min_m(lhs, rhs) result(res)
    type(modint), intent(in) :: lhs, rhs
    res = lhs
    if (rhs%to_i64() < lhs%to_i64()) res = rhs
  end function min_m
  pure type(modint) function max_m(lhs, rhs) result(res)
    type(modint), intent(in) :: lhs, rhs
    res = lhs
    if (rhs%to_i64() > lhs%to_i64()) res = rhs
  end function max_m
end module modint_m
program f902380
  use, intrinsic :: iso_fortran_env
  !> auto use module
  use modint_m
  use modint_m
  implicit none
  integer(int32), parameter :: maxi_b = 50
  integer(int64) :: n, p
  integer(int64) :: cnts2
  integer(int32) :: i
  read(input_unit, *) n, p
  cnts2 = 0_int64
  do i = 1, maxi_b
     associate(two_expo_r64 => real(p, real64) ** i)
       if (two_expo_r64 > 1d18) exit
     end associate
     !> two_expo <= 10 ** 18.
     associate(two_expo => p ** i)
       if (two_expo > n) exit
       cnts2 = cnts2 + n / two_expo
     end associate
  end do
  !> n! == p^cnts2 * k
  !> 位数は p^cnts2
  write(output_unit, '(i0)') modint(p) ** cnts2
end program f902380