#1184647 (Crystal) No.3686 Coprime Sum

提出ソース
結果

問題	No.3686 Coprime Sum
コンテスト
ユーザー	かざり
提出日時	2026-09-06 23:33:52
言語	Crystal (1.21.0 + ACL) コンパイル: `crystal build -Donline_judge -o a.out --release --no-debug _filename_` 実行: `./a.out`
結果	AC
実行時間	494 ms / 2,000 ms
	+ 362µs
コード長	23,026 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	9,157 ms
コンパイル使用メモリ	345,224 KB
実行使用メモリ	25,216 KB
最終ジャッジ日時	2026-09-06 23:34:05
合計ジャッジ時間	13,298 ms
ジャッジサーバーID （参考情報）	judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 10
権限があれば一括ダウンロードができます
ソースコード

raw source code
macro pt(s);pointerof({{s}});end
struct Time;def diff(other : Time);(self-other).abs.total_milliseconds;end;end
struct Bool;def to_i;self ? 1 : 0;end;end
macro vgen(*v);Array.new({{v[0]}}){ {% if v.size==2 %}{{v[1]}}{% else %}vgen({{v[1..].splat}}){% end %} };end
macro rvgen(type,*v);{% if v.size==2 %}Array({{type}}).new({{v[0]}}){{{v[1]}}}{% else %}Array.new({{v[0]}}){rvgen({{type}},{{v[1..].splat}})}{% end %};end
def max(a,b);a<b ? b : a;end
def min(a,b);a<b ? a : b;end
def max(*a);x=a[0];(1...a.size).each{|i|x=max(x,a[i])};x;end
def min(*a);x=a[0];(1...a.size).each{|i|x=min(x,a[i])};x;end
macro chmin(a,b);(%t={{b}};{{a}}>%t ? ({{a}}=%t;true) : false);end
macro chmax(a,b);(%t={{b}};{{a}}<%t ? ({{a}}=%t;true) : false);end
macro swap(a,b);{{a}},{{b}}={{b}},{{a}};end
def assert(cond : Bool, msg = "Assertion failed");raise msg unless cond;end
TF = {true, false}
def yn(cond)
	ios.outl cond ? "Yes" : "No"
end
macro for(f, m, s);begin
	{{f}}
	while {{m}}
		begin
			{{yield}}
		ensure
			{{s}}
		end
	end
end;end
struct Int
	def each_subset(&)
		s = self
		loop do
			yield s
			s = s - 1 & self
			break if s == self
		end
	end
end
module Indexable(T)
	def [](c : Bool); self[c ? 1 : 0]; end
	def []=(c : Bool, v : T); self[c ? 1 : 0] = v; end
end
require "big"
lib LibIOset
  fun memcpy(dest : Void*, src : Void*, n : UInt64) : Void*
  fun read(fd : Int32, buf : Void*, count : UInt64) : Int64
  fun write(fd : Int32, buf : Void*, count : UInt64) : Int64
  fun fcntl(fd : Int32, cmd : Int32, ...) : Int32
  F_GETFL = 3
  F_SETFL = 4
  O_NONBLOCK = 0o4000
end
class IOset
  BUFS = 1 << 20
  OT = Pointer(UInt32).malloc(10000)
  POW10 = {1i64, 10i64, 100i64, 1000i64, 10000i64, 100000i64, 1000000i64, 10000000i64, 100000000i64, 1000000000i64, 10000000000i64, 100000000000i64, 1000000000000i64, 10000000000000i64, 100000000000000i64 , 1000000000000000i64, 10000000000000000i64}
  REV = StaticArray(UInt32, 10).new(0u32)
  @buf = Pointer(UInt8).malloc BUFS; @obuf = Pointer(UInt8).malloc BUFS; @precision = 10
  @ptr : UInt8*; @end : UInt8*; @optr : UInt8*; @oend : UInt8*
  @in_io : IO = STDIN; @out_io : IO = STDOUT; @in_fd = 0; @out_fd = 1
  def initialize
    10u32.times { |a| 10.times { |b| 10.times { |c| 10.times { |d| OT[a * 1000 + b * 100 + c * 10 + d] = a + 48 | b + 48 << 8 | c + 48 << 16 | d + 48 << 24 } } } }
    force_blocking(0)
    force_blocking(1)
    @ptr = @buf
    @end = @buf
    @optr = @obuf
    @oend = @obuf + BUFS
  end
  def set_io(input : IO = STDIN, output : IO = STDOUT) : Nil
    @in_io = input; @out_io = output
    @in_fd = input.is_a?(IO::FileDescriptor) ? input.fd : -1
    @out_fd = output.is_a?(IO::FileDescriptor) ? output.fd : -1
    force_blocking(@in_fd)
    force_blocking(@out_fd)
  end
  private def force_blocking(fd : Int32) : Nil
    return if fd < 0
    flags = LibIOset.fcntl(fd, LibIOset::F_GETFL)
    if flags >= 0
      LibIOset.fcntl(fd, LibIOset::F_SETFL, flags & ~LibIOset::O_NONBLOCK)
    end
  end
  def fill : Nil
    if @in_fd < 0
      res = @in_io.read Slice.new @buf, BUFS
      @end = @buf + res
    else
      res = LibIOset.read(@in_fd, @buf.as(Void*), BUFS)
      @end = @buf + (res < 0 ? 0 : res.to_i)
    end
    @ptr = @buf
  end
  def eof? : Bool
    fill if @end <= @ptr; @ptr == @end
  end
  def read_byte : UInt8?
    fill if @end <= @ptr; return nil if @ptr == @end; b = @ptr.value; @ptr += 1; b
  end
  def trim : Nil
    iptr = @ptr
    loop do
      (fill; iptr = @ptr) if @end <= iptr
      break if iptr == @end || 32 < iptr.value
      iptr += 1
    end
    @ptr = iptr
  end
  def trim? : Bool
    trim
    !eof?
  end
  def getc : Char
    fill if @end <= @ptr
    c = nil.as(UInt8?)
    iptr = @ptr
    if iptr == @end
      c = nil
    else
      c = iptr.value; iptr += 1
    end
    while c && c <= 32
      (fill; iptr = @ptr) if @end <= iptr
      if iptr == @end
        c = nil
      else
        c = iptr.value; iptr += 1
      end
    end
    raise "End of file reached (IOset.getc)" if !c
    @ptr = iptr
    c.not_nil!.chr
  end
  def read_line : String
    raise "End of file reached (IOset.read_line)" if @end <= @ptr && (fill; @end <= @ptr)
    iptr = @ptr
    start = iptr
    while iptr < @end && iptr.value != 10
      iptr += 1
    end
    if iptr < @end
      len = iptr - start
      @ptr = iptr + 1
      return String.new(start, len)
    end
    @ptr = iptr
    String.build do |io|
      io.write Slice.new(start, (@end - start).to_i)
      while (b = read_byte) && b != 10
        io.write_byte b
      end
    end
  end
  def gets : String
    trim
    raise "End of file reached (IOset.gets)" if @end <= @ptr && (fill; @end <= @ptr)
    iptr = @ptr
    start = iptr
    while iptr < @end && iptr.value > 32
      iptr += 1
    end
    if iptr < @end
      len = iptr - start
      @ptr = iptr
      return String.new(start, len)
    end
    @ptr = iptr
    String.build do |io|
      io.write Slice.new(start, (@end - start).to_i)
      while (b = read_byte) && b > 32
        io.write_byte b
      end
    end
  end
  def gets? : String?
    trim
    return nil if @end <= @ptr && (fill; @end <= @ptr)
    iptr = @ptr
    start = iptr
    while iptr < @end && iptr.value > 32
      iptr += 1
    end
    if iptr < @end
      len = iptr - start
      @ptr = iptr
      return String.new(start, len)
    end
    @ptr = iptr
    String.build do |io|
      io.write Slice.new(start, (@end - start).to_i)
      while (b = read_byte) && b > 32
        io.write_byte b
      end
    end
  end
  macro geti_g(name, type)
    def {{name}} : {{type}}
      trim
      iptr = @ptr
      sign = 1
      if iptr.value == 45
        sign = -1; iptr += 1
        (fill; iptr = @ptr) if @end <= iptr
      end
      n = {{type}}.zero
      while iptr + 8 <= @end
        tmp = iptr.as(UInt64*).value
        break if ((tmp &-= 0x3030303030303030_u64) & 0x8080808080808080_u64) != 0
        tmp = (tmp &* 10 &+ (tmp >> 8)) & 0x00ff00ff00ff00ff_u64
        tmp = (tmp &* 100 &+ (tmp >> 16)) & 0x0000ffff0000ffff_u64
        tmp = (tmp &* 10000 &+ (tmp >> 32)) & 0x00000000ffffffff_u64
        n = n &* 100000000 &+ tmp
        iptr += 8
      end
      while iptr < @end || (fill; iptr = @ptr; iptr < @end)
        c = iptr.value &- 48u8
        break if 9u8 < c
        n = n &* 10 &+ c
        iptr += 1
      end
      @ptr = iptr
      n &* sign
    end
  end
  geti_g(geti8, Int8); geti_g(getu8, UInt8); geti_g(geti16, Int16); geti_g(getu16, UInt16)
  geti_g(geti, Int32); geti_g(getu, UInt32); geti_g(getbi, BigInt)
  geti_g(geti64, Int64); geti_g(getu64, UInt64); geti_g(geti128, Int128); geti_g(getu128, UInt128)
  def geti32; geti; end; def getu32; getu; end
  # ---output---
  def write_byte(b : UInt8) : Nil
    flush if @optr == @oend; @optr.value = b; @optr += 1
  end
  def write(s : String) : Nil
    size = s.bytesize
    z = s.to_unsafe
    i = 0
    flush if @oend == @optr
    while @oend - @optr <= size - i
      len = @oend - @optr
      LibIOset.memcpy(@optr.as(Void*), (z + i).as(Void*), len)
      i += len
      @optr = @oend
      flush
    end
    if 0 < size - i
      LibIOset.memcpy(@optr.as(Void*), (z + i).as(Void*), size - i)
      @optr += size - i
    end
  end
  macro wi_core_g(bit)
    @[AlwaysInline]
    private def write_int_core{{bit.id}}(n1 : UInt{{bit.id}}, optr : UInt8*) : Nil
      if n1 == 0
        optr.value = 48u8
        @optr = optr + 1
        return
      end
      t_idx = 0
      while 10000 <= n1
        n0 = n1 // 10000
        REV[t_idx] = OT[n1 - n0 * 10000]
        n1 = n0
        t_idx += 1
      end
      n = n1.to_i16
      if 1000 <= n
        optr.as(UInt32*).value = OT[n]
        optr += 4
      elsif 100 <= n
        v = OT[n]
        optr[0] = (v >> 8).to_u8!
        optr[1] = (v >> 16).to_u8!
        optr[2] = (v >> 24).to_u8!
        optr += 3
      elsif 10 <= n
        v = OT[n]
        optr[0] = (v >> 16).to_u8!
        optr[1] = (v >> 24).to_u8!
        optr += 2
      else
        optr.value = 48u8 + n
        optr += 1
      end
      while 0 < t_idx
        optr.as(UInt32*).value = REV[t_idx -= 1]
        optr += 4
      end
      @optr = optr
    end
  end
  wi_core_g(8); wi_core_g(16); wi_core_g(32); wi_core_g(64); wi_core_g(128)
  macro write_int_g(bit)
    def write_int(x : Int{{bit.id}}) : Nil
      flush if @optr + 25 > @oend
      optr = @optr
      if x < 0
        optr.value = 45u8; optr += 1
        write_int_core{{bit.id}} ~x.unsafe_as(UInt{{bit.id}}) &+ 1, optr
      else
        write_int_core{{bit.id}} x.unsafe_as(UInt{{bit.id}}), optr
      end
    end
    def write_int(x : UInt{{bit.id}}) : Nil
      flush if @optr + 25 > @oend
      write_int_core{{bit.id}} x, @optr
    end
  end
  write_int_g(8); write_int_g(16); write_int_g(32); write_int_g(64)
  def write_int(x : Int128) : Nil
    flush if @optr + 45 > @oend
    optr = @optr
    if x < 0
      optr.value = 45u8; optr += 1
      write_int_core128 ~x.unsafe_as(UInt128) &+ 1, optr
    else
      write_int_core128 x.unsafe_as(UInt128), optr
    end
  end
  def write_int(x : UInt128) : Nil
    flush if @optr + 45 > @oend
    write_int_core128 x, @optr
  end
  def write_int(x : BigInt) : Nil; write x.to_s; end
  def setprecision(x) : Nil
    raise ArgumentError.new("precision shold be greater than 0 and less than 17") if x < 0 || 16 < x
    @precision = {x.to_i, 16}.min
  end
  def write_float(x : Float) : Nil
    flush if @optr + 50 > @oend
    if x < 0
      @optr.value = 45u8
      @optr += 1
      x = -x
    end
    prec = @precision
    write_int x.to_i64
    return if prec == 0
    optr = @optr
    optr.value = 46_u8
    optr += 1
    f = ((x - x.to_i64) * POW10.unsafe_fetch(prec)).to_i64
    cur = optr + prec
    while 4 <= cur - optr
      f0 = f // 10000
      rem = (f - f0 * 10000).to_i
      f = f0
      cur -= 4
      cur.as(UInt32*).value = OT[rem]
    end
    while optr < cur
      cur -= 1
      f0 = f // 10
      cur.value = (f - f0 * 10).to_u8 + 48u8
      f = f0
    end
    @optr = optr + prec
  end
  def flush : Nil
    return if @optr == @obuf
    size = @optr - @obuf
    if @out_fd < 0
      @out_io.write Slice.new @obuf, size
    else
      LibIOset.write @out_fd, @obuf.as(Void*), size
    end
    @optr = @obuf
  end
  def putv(x : Array(Array(T))) : Nil forall T
    return if x.empty?
    putv x.unsafe_fetch 0
    (1...x.size).each { |i| write_byte 10u8; putv x.unsafe_fetch i }
  end
  def putv(x : Array(Tuple)) : Nil
    return if x.empty?
    putv x.unsafe_fetch 0
    (1...x.size).each { |i| write_byte 10u8; putv x.unsafe_fetch i }
  end
  def putv(x : Int) : Nil; write_int x; end
  def putv(x : Char) : Nil; write_byte x.ord.to_u8; end
  def putv(x : Float) : Nil; write_float x; end
  def putv(x : String) : Nil; write x; end
  def putv(x : Bool) : Nil; write_byte x ? 49u8 : 48u8; end
  def putv(x : Indexable(T)) : Nil forall T
    return if x.empty?
    putv x.unsafe_fetch 0
    (1...x.size).each { |i| write_byte 32u8; putv x.unsafe_fetch i }
  end
  def print(*x) : Nil
    x.each { |v| putv v }
  end
  def outl(*x, sep : (String | Char) = ' ', endl : (String | Char) = '\n') : Nil
    if f = x.first?
      putv f
      (1...x.size).each { |i| putv sep; putv x.unsafe_fetch i }
    end
    putv endl
  end
end
IOSETi = IOset.new
@[AlwaysInline]; def ios; IOSETi; end
at_exit { ios.flush }
macro fmodint_gen(name, max_mod = 0xfffffffffffu64)
  {% if max_mod <= 0xffffffffu64 %}
    {% u_tp = "UInt32".id %}
    {% d_tp = "UInt64".id %}
    {% us = "to_u32!".id %}
    {% ds = "to_u64!".id %}
    {% ss = "to_i64!".id %}
    {% bits = 32 %}
  {% else %}
    {% u_tp = "UInt64".id %}
    {% d_tp = "UInt128".id %}
    {% us = "to_u64!".id %}
    {% ds = "to_u128!".id %}
    {% ss = "to_i128!".id %}
    {% bits = 64 %}
  {% end %}
  struct {{name}}
    BITS = {{bits}}
    @@p : {{u_tp}} = 1.{{us}}
    @@p2 : {{u_tp}} = 1.{{us}} << 1
    @@r : {{u_tp}} = 0.{{us}}
    @@r2 : {{u_tp}} = 0.{{us}}
    property v : {{u_tp}}
    @v = 0.{{us}}
    # reduce(x)=x/W
    @[AlwaysInline]
    def self.reduce(x : {{d_tp}})
      ((x &+ (x.{{us}} &* @@r).{{ds}} * @@p) >> BITS).{{us}}
    end
    def self.set_mod(mod)
      @@p = mod.{{us}}
      @@p2 = @@p << 1
      @@r = begin
            y = @@p;6.times{ y &*= 2.{{us}} &- @@p &* y }
            &-y
          end
      @@r2 = (&-@@p.{{ds}} % @@p).{{us}}
    end
    def self.mod
      @@p
    end
    def self.max; new -1; end
    def self.min; new 0; end
    def self.zero
      new 0
    end
    def zero?
      val == 0
    end
    def val
      x = self.class.reduce @v
      x &- @@p >> BITS - 1 == 0 ? x - @@p : x
    end
    def to_i;val;end
    def initialize;@v = 0;end
    def initialize(x : Int::Signed);@v = self.class.reduce((x.{{ss}} % @@p).{{ds}} * @@r2);end
    def initialize(x : Int);@v = self.class.reduce((x.{{ds}} % @@p).{{ds}} * @@r2);end
    def initialize(x : {{u_tp}}, d);@v = x;end
    def initialize(x : self);@v = x.v;end
    def ==(other : self)
      val == other.val
    end
    def -
        @v == 0 ? self.class.new(0.{{us}}, 0) : self.class.new(@@p2 - @v, 0)
    end
    def +(other : self)
      z = self.class.new(@v &+ other.v, 0)
      z.v &-= @@p2 if z.v &- @@p2 >> BITS - 1 == 0
      z
    end
    def -(other : self)
      z = self.class.new(@v &- other.v, 0)
      z.v &+= @@p2 if z.v >> BITS - 1 != 0
      z
    end
    def *(other : self)
      self.class.new(self.class.reduce(@v.{{ds}}*other.v), 0)
    end
    def /(other : self)
      self * other.inv
    end
    def +(other : Int);self + self.class.new(other);end
    def -(other : Int);self - self.class.new(other);end
    def *(other : Int);self * self.class.new(other);end
    def /(other : Int);self / self.class.new(other);end
    def ==(other : Int);val == other;end
    def pow(k)
      res = self.class.new(1)
      a = self
      while k != 0
        res *= a if k & 1 != 0
        k >>= 1
        a *= a
      end
      res
    end
    def inv
      self.class.new modinv val.to_i64, @@p.to_i64
    end
  end
  class IOset
    def putv(x : {{name}});write_int x.val;end
  end
  struct Int
    def +(other : {{name}});other + self;end
    def -(other : {{name}});-other + self;end
    def *(other : {{name}});other * self;end
    def /(other : {{name}});other.inv * self;end
    def ==(other : {{name}});other == self;end
  end
end
fmodint_gen(Fmodint)
def inv_gcd(a : Int64, m : Int64)
  a %= m
  b = m
  # track M = |u t| such that M * |a| = |gcd(a b)| => au + bt = gcd(a b)
  #           |v _|               |b|   |0       |

  # identity matrix
  u, v = 1i64, 0i64
  while b != 0
    q = a // b
    # r = a - q * b = a % b
    # |0  1| * |a| = |b|
    # |1 -q|   |b|   |r|
    a, b = b, a - q * b
    # |0  1| * |u _| = |v    _|
    # |1 -q|   |v _|   |u-vq _|
    u, v = v, u - v * q
  end
  {u % m, a}
end

def ext_gcd(a : Int64, b : Int64) : {Int64, Int64, Int64}
  return {a.abs, a < 0 ? -1i64 : (a > 0 ? 1i64 : 0i64), 0i64} if b == 0
  an, bn = a < 0 , b < 0
  a, b = a.abs, b.abs
  a_in, b_in = a, b
  u, v = 1i64, 0i64
  while b != 0
    q = a // b
    a, b = b, a - q * b
    u, v = v, u - v * q
  end
  x = u
  y = (a - a_in * x) // b_in
  {a, an ? -x : x, bn ? -y : y}
end

def modinv(a : Int64, m : Int64)
  u, d = inv_gcd(a, m)
  d == 1 ? u : 0
end

#     x = m0*k + r0
#     x = r1 mod m1
# <=> m0*k + r0 = r1 mod m1
# <=> m0*k = r1 - r0 mod m1
# <=> m0/d*k = (r1- r0)/d mod m1/d where d = gcd(m0 m1), require d | r1 - r0
# <=> k = (r1 - r0)/d*(m0/d)^-1 mod m1/d
def crt(r : Array(Int64), m : Array(Int64))
  r0, m0 = 0i64, 1i64
  r.each_with_index do |r1, i|
    m1 = m[i]
    r1 %= m1
    if m0 < m1
      r0, r1 = r1, r0
      m0, m1 = m1, m0
    end
    if m0 % m1 == 0
      return {0i64, 0i64} if r0 % m1 != r1
      next
    end
    u, d = inv_gcd m0, m1
    return {0i64, 0i64} if (r1 - r0) % d != 0
    ms = m1 // d
    k = (r1 - r0) // d * u % ms
    r0 += m0 * k
    m0 *= ms
    r0 %= m0
  end
  {r0, m0}
end

def modpow(a : Int64, p : Int64, m : Int64 = 998244353)
  res = 1i64
  a %= m
  while p != 0
    res = res * a % m if p & 1 != 0
    p >>= 1
    a = a * a % m
  end
  res
end

# n以下の逆元列挙
def linear_modinv(n : Int, m : Int64 = 998244353)
  res = Array.new n + 1, 1i64
  z = res.to_unsafe
  2.upto(n) do |k|
    # q * k + r = 0 <=> q * 1/r = -1/k <=> 1/k = -q * 1/r
    q = m // k
    z[k] = -(q * z[m - q * k]) % m
  end
  res
end

# for prime numbers
# return minimum number g such that i!=j => g^i!=g^j
def primitive_root(n : Int64) : Int64
  return 1i64 if n == 2
  p = n - 1
  d = StaticArray(Int64, 20).new 0
  d[0] = 2
  c = 1
  x = p
  while x & 1 == 0;x >>= 1;end
  i = 3i64
  loop do
    break if x < i * i
    (i += 2;next) if x % i != 0
    d[c] = i
    c += 1
    while x % i == 0;x //= i;end
    i += 2
  end
  (d[c] = x;c += 1) if 1 < x
  (2i64..p).each do |g|
    f = true
    c.times do |i|
      # i!=j => g^i!=g^j && g^p=1
      if modpow(g, p // d[i], n) == 1
        f = false
        break
      end
    end
    return g if f
  end
  -1i64
end

# return x such that a^x = b mod m, that is, log_a b mod m
#     a^x = b mod m && iu-j = x
# <=> a^{iu-j}=b mod m
# <=> (a^u)^i=ba^j mod m
# require gcd(g m) = 1
def discrete_log(a : Int64, b : Int64, m : Int64)
  a %= m; b %= m
  return 0i64 if b == 1
  u = Math.isqrt(m - 1) + 1
  # 右辺
  map = Hash(Int64, Int64).new u
  y = b
  (0i64...u).each do |j|
    map[y] = j
    y = y * a % m
  end
  # 左辺
  base = x = modpow a, u, m
  (1i64..u).each do |i|
    if j = map[x]?
      return i * u - j
    end
    x = x * base % m
  end
  -1i64
end

def floor_sum(n, m, a, b)
  s = a // m
  a -= s * m
  s *= n * (n - 1) >> 1
  sb = b // m
  s += sb * n
  return s if a == 0
  b -= sb * m
  k = (a * (n - 1) + b) // m
  s + n * k - floor_sum(k, a, m, m + a - b - 1)
end

def kroot(a : Int64, b : Int64) : Int64
  return 0 if a == 0
  return a if b == 1
  x = 1i64 << ((a.bit_length + b - 1) // b)
  while true
    nex = ((b - 1) * x + a // (x ** (b - 1))) // b
    return x if x <= nex
    x = nex
  end
end

# pは素数であることを仮定
# aが平方剰余でなければ-1を返す。
def mod_sqrt(a : Int64, p : Int64) : Int64
  a %= p
  return a if p == 2 || a < 2
  return -1 if modpow(a, p - 1 >> 1, p) != 1
  return modpow(a, p + 1 >> 2, p) if p & 3 == 3
  # https://nyaannyaan.github.io/library/modulo/mod-sqrt.hpp.html
  # a^((p-1)/2)=1 (mod p)が成り立つ
  # 原子根rについてx=r^y, a=r^bとすると、
  # x^2=a (mod p) <=> 2y = b (mod p - 1)
  # p - 1 = s * 2^t (sは奇数) として
  # crtよりmod s, mod 2^tにおいて2y = bが成り立てばよい
  # xの初期値をa^((s+1)/2)とすれば、y=(s+1)/2*b (mod p - 1)
  # sは奇数なので、mod sでは成り立っている。
  # 平方剰余でないuを一つ選ぶと、(乱択の回数の期待値は2)
  # Ind_r(u^x) = 0 (mod s), Ind_r(u^x) = 1 (mod 2)
  # a^-1x^2を1にしたいが、a^-1x^2=r^(2y-b) (mod p)である。
  # a^-1x^2をt'回二乗して1になるならば、Eが2^tの倍数である。これはt-p_v(E)に等しい。よって、誤差Eの最下位ビットの位置k=p_v(E)を特定できた。
  # あとは、2^(k-1)乗すればよい
  # 誤差修正回数、累乗計算ともにO(log p)
  fmodint_gen(Fmod_sqrt, p)
  Fmod_sqrt.set_mod(p)
  u = Fmod_sqrt.new 1
  while u.pow(p - 1 >> 1) == 1
    u += 1
  end
  s, t = p - 1, 0i64
  while s & 1 == 0
    s >>= 1; t += 1
  end
  x = Fmod_sqrt.new(a).pow(s - 1 >> 1)
  y = x * x * a
  x *= a
  us = u.pow(s)
  while y != 1
    t_ = 0i64
    error = y
    while error != 1
      t_ += 1
      error *= error
    end
    to_add = us.pow(1i64 << t - t_ - 1)
    x *= to_add
    us = to_add * to_add
    y *= us
    t = t_
  end
  x.v
end
macro modint_gen(name, mod)
  {% if mod <= 0xffffffffu64 %}
    {% u_tp = "UInt32".id %}
    {% d_tp = "UInt64".id %}
    {% us = "to_u32!".id %}
    {% ds = "to_u64!".id %}
    {% ss = "to_i64!".id %}
    {% bits = 32 %}
  {% else %}
    {% u_tp = "UInt64".id %}
    {% d_tp = "UInt128".id %}
    {% us = "to_u64!".id %}
    {% ds = "to_u128!".id %}
    {% ss = "to_i128!".id %}
    {% bits = 64 %}
  {% end %}
  struct {{name}}
    BITS = {{bits}}
    # W = 2^BIT
    P = {{mod}}.{{us}}
    P2 = P << 1
    # 1 / y - P = 0
    R = begin
          y = P;6.times{ y &*= 2.{{us}} &- P &* y }
          &-y
        end
    # (W^2 - P) % P = W^2 % P
    R2 = (&-P.{{ds}} % P).{{us}}
    MAX = new(-1)
    MIN = new(0)
    property v : {{u_tp}}
    @v = 0.{{us}}
    # reduce(x)=x/W
    @[AlwaysInline]
    def self.reduce(x : {{d_tp}})
      ((x &+ (x.{{us}} &* R).{{ds}} * P) >> BITS).{{us}}
    end
    def self.mod
      P
    end
    def self.zero
      new 0
    end
    def zero?
      val == 0
    end
    def val
      x = self.class.reduce @v
      x &- P >> BITS - 1 == 0 ? x - P : x
    end
    def to_i;val;end
    def initialize;@v = 0;end
    def initialize(x : Int::Signed);@v = self.class.reduce((x.{{ss}} % P).{{ds}} * R2);end
    def initialize(x : Int);@v = self.class.reduce((x.{{ds}} % P).{{ds}} * R2);end
    def initialize(x : {{u_tp}}, d);@v = x;end
    def initialize(x : self);@v = x.v;end
    def ==(other : self)
      val == other.val
    end
    def -
        @v == 0 ? self.class.new(0.{{us}}, 0) : self.class.new(P2 - @v, 0)
    end
    def +(other : self)
      z = self.class.new(@v &+ other.v, 0)
      z.v &-= P2 if z.v &- P2 >> BITS - 1 == 0
      z
    end
    def -(other : self)
      z = self.class.new(@v &- other.v, 0)
      z.v &+= P2 if z.v >> BITS - 1 != 0
      z
    end
    def *(other : self)
      self.class.new(self.class.reduce(@v.{{ds}}*other.v), 0)
    end
    def /(other : self)
      self * other.inv
    end
    def +(other : Int);self + self.class.new(other);end
    def -(other : Int);self - self.class.new(other);end
    def *(other : Int);self * self.class.new(other);end
    def /(other : Int);self / self.class.new(other);end
    def ==(other : Int);val == other;end
    def pow(k)
      res = self.class.new(1)
      a = self
      while k != 0
        res *= a if k & 1 != 0
        k >>= 1
        a *= a
      end
      res
    end
    def inv
      self.class.new modinv val.to_i64, P.to_i64
    end
  end
  class IOset
    def putv(x : {{name}});write_int x.val;end
  end
  struct Int
    def +(other : {{name}});other + self;end
    def -(other : {{name}});-other + self;end
    def *(other : {{name}});other * self;end
    def /(other : {{name}});other.inv * self;end
    def ==(other : {{name}});other == self;end
  end
end
modint_gen(F998244353, 998244353)
alias F = F998244353
n, m = ios.geti, ios.geti
swap(n, m) if n > m
mus = [1i8]*(n + 1)
seen = [false]*(n + 1)
mus[0i8] = 0
i = 2i64
for 0, i <= n, i += 1 do
  next if seen[i]
  for p = i * i, p <= n, p += i * i do
    seen[p] = true
    mus[p] = 0i8
  end
  for p = i, p <= n, p += i do
    seen[p] = true
    mus[p] *= -1i8
  end
end
answer = F.zero
1.upto(n) do |i|
  answer += F.new(mus[i]) * i * i / 4 * (n // i) * (n // i + 1) * (m // i) * (m // i + 1)
end
ios.outl answer
yukicoder

結果

ソースコード
