SRM 535 Div II

SRM 535 Div II

  • 初参加したSRMにて惨敗した問題に挑戦。今でも自分には中々難しく、35分ほど時間を要した

FromAndGCDLCM

  • 未知の数AとBの最大公約数と最小公倍数、GとLが与えられる。ここからAとBを推測し、その最小の和(A + B)を返す問題
  • 最大公約数Gと最小公倍数Lに有効なAとBが存在しなければ-1を返す
  • 問題を見てまずぱっと思い浮かべた式は以下だ


  • AとBは[1, 1012]を取る値だ。そのため、上述の左辺が1024を取りうる。これは約1,0008、約280の値だ。素直に実装したらlong longから溢れてしまう
  • さて、上述の式を変形すると、以下となる。


  • 問題に習い、lcm(A, B)L、gcd(A, B)をGとすると、右辺はLGとすることが出来る。
  • AとBを乗してLGとなるようなAとBの組み合わせを求めるような実装は大抵、以下のような形となることが多い。計算量はO(√LG)だ
  for (int i = 1; i * i <= LG; i ++)
                    :
  • さて、この場合、AはGの倍数である。またlong longであることを加味すると、つまり、この実装は以下のような形になると思われる
  for (long long A = G; A * A <= LG; G ++)
                    :
  • LGがlong longに納まりきらないことを承知の上で実装を進めると、以下となる(最大公約数を今一度求めるのは実装をテストして気付いた。サンプルになければWAを出していたところだ)
  long long nm = INF;

  for (long long A = G; A * A <= LG; G ++)
    if (LG % A == 0) {
      long long B = LG / A;

      if (std::__gcd(A, B) == G)
        nm = std::min(A + B, nm);
    }
  • 繰り返すが、A・AやLGはlong longに収まらない。そのため、何らかの回避策を取る必要がある
  • AをiGと表すことにする。iを倍数として、long longから溢れさせないようにする作戦だ


  • 難しいのは反復の条件だ。A = iGとすると、以下とすることができる


  • また、iからBを求めるには以下とする


  long long nm = INF;

  for (long long i = 1; i * i <= L / G; i ++) {
    long long A = i * G;

    if (L % i == 0) {
      long long B = L / i;

      if (std::__gcd(A, B) == G)
        nm = std::min(A + B, nm);
    }
  }

まとめ

  • SRM参戦時に惨敗した問題。解けて素直に嬉しく思うと共に、Div II Mediumとしてはなかなか難しく、またとても良問であったように思えた
  • A、B、lcm(A, B)、gcd(A, B)を考えるとき、以下の関係式は大変重宝する


  • 積がNとなるようなiとjを組み合わせる際の典型の実装は以下となり、その計算量はO(√N)である
  for (int i = 1; i * i <= N; i ++)
    if (N % i == 0) {
      int j = N / i;
            :
    }