結果

問題 No.1529 Constant Lcm
コンテスト
ユーザー yuruhiya
提出日時 2021-06-05 20:31:01
言語 Crystal
(1.14.0)
結果
AC  
実行時間 622 ms / 3,000 ms
コード長 4,276 bytes
コンパイル時間 15,972 ms
コンパイル使用メモリ 294,752 KB
実行使用メモリ 14,852 KB
最終ジャッジ日時 2024-11-21 19:20:40
合計ジャッジ時間 19,778 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

# require "math/Sieve"
class Sieve
  getter size : Int32
  getter factor : Array(Int32)
  getter primes : Array(Int32)

  def initialize(@size)
    @factor = Array(Int32).new(@size + 1, 0)
    @primes = [] of Int32
    sqrt_size = Math.sqrt(@size).to_i + 1
    (2..size).each do |x|
      next unless @factor[x] == 0
      @factor[x] = x
      @primes << x
      next if sqrt_size < x
      (x * x).step(to: size, by: x) { |y|
        @factor[y] = x if @factor[y] == 0
      }
    end
  end

  def prime?(x)
    factor[x] == x
  end

  private class PrimeDivisionIterator
    include Iterator({Int32, Int32})

    def initialize(@current : Int32, @factor : Array(Int32))
    end

    def next
      return stop if @current == 1
      element = @factor[@current]
      count = 0
      while @current != 1 && @factor[@current] == element
        count += 1
        @current //= element
      end
      {element, count}
    end
  end

  def prime_division(x)
    PrimeDivisionIterator.new(x, factor)
  end

  def each_factor(x, &) : Nil
    while x > 1
      element = @factor[x]
      count = 0
      while x != 1 && @factor[x] == element
        count += 1
        x //= element
      end
      yield(element, count)
    end
  end
end

# require "math/Mint"
macro static_modint(name, mod)
  struct {{name}}
    MOD = Int64.new({{mod}})

    def self.zero
      new
    end

    def self.raw(value : Int64)
      result = new
      result.value = value
      result
    end

    @value : Int64

    def initialize
      @value = 0i64
    end

    def initialize(value)
      @value = value.to_i64 % MOD
    end

    def initialize(m : self)
      @value = m.value
    end

    protected def value=(value : Int64)
      @value = value
    end

    getter value : Int64

    def + : self
      self
    end

    def - : self
      self.class.raw(value != 0 ? MOD &- value : 0i64)
    end

    def +(v)
      self + v.to_m
    end

    def +(m : self)
      x = value &+ m.value
      x &-= MOD if x >= MOD
      self.class.raw(x)
    end

    def -(v)
      self - v.to_m
    end

    def -(m : self)
      x = value &- m.value
      x &+= MOD if x < 0
      self.class.raw(x)
    end

    def *(v)
      self * v.to_m
    end

    def *(m : self)
      self.class.new(value &* m.value)
    end

    def /(v)
      self / v.to_m
    end

    def /(m : self)
      raise DivisionByZeroError.new if m.value == 0
      a, b, u, v = m.to_i64, MOD, 1i64, 0i64
      while b != 0
        t = a // b
        a &-= t &* b
        a, b = b, a
        u &-= t &* v
        u, v = v, u
      end
      self.class.new(value &* u)
    end

    def //(v)
      self / v
    end

    def **(exponent : Int)
      t, res = self, self.class.raw(1i64)
      while exponent > 0
        res *= t if exponent & 1 == 1
        t *= t
        exponent >>= 1
      end
      res
    end

    def ==(m : self)
      value == m.value
    end

    def ==(m : Int)
      raise NotImplementedError.new("==")
    end

    {% for op in %w[< <= > >=] %}
      def {{op.id}}(other)
        raise NotImplementedError.new({{op}})
      end
    {% end %}

    def succ
      self.class.raw(value != MOD &- 1 ? value &+ 1 : 0i64)
    end

    def pred
      self.class.raw(value != 0 ? value &- 1 : MOD &- 1)
    end

    def abs
      self
    end

    def to_i64 : Int64
      value
    end

    delegate to_s, to: @value
    delegate inspect, to: @value
  end

  struct Int
    {% for op in %w[+ - * / //] %}
      def {{op.id}}(value : {{name}})
        to_m {{op.id}} value
      end
    {% end %}

    {% for op in %w[== != < <= > >=] %}
      def {{op.id}}(m : {{name}})
        raise NotImplementedError.new({{op}})
      end
    {% end %}

    def to_m : {{name}}
      {{name}}.new(self)
    end
  end

  class String
    def to_m : {{name}}
      {{name}}.new(self)
    end
  end
end

static_modint(Mint, 998244353)
n = read_line.to_i
sieve = Sieve.new(n)
max = Hash(Int32, Int32).new(0)
(1...n).each do |x|
  hash = Hash(Int32, Int32).new(0)
  sieve.each_factor(x) { |elem, cnt| hash[elem] += cnt }
  sieve.each_factor(n - x) { |elem, cnt| hash[elem] += cnt }
  hash.each { |elem, cnt| max[elem] = {max[elem], cnt}.max }
end
puts max.reduce(Mint.new(1)) { |acc, (elem, cnt)|
  acc * Mint.new(elem)**cnt
}
0