https://bcu30-2018.contest.atcoder.jp/tasks/bcu30_2018_a

概要

(現状問題公開されてないですからね…)

1個ずつ数字が書かれた球がA個ある。これを1個ずつ数字が書かれたB個の球にしたい。ただし変換は以下の2種類。

  • 数xと数yが書かれた2個の球を数x * yが書かれた1個の球にする
  • 数xが書かれた1個の球を、(x%y==0となるような適当なyを選んで)数yと数x / yが書かれた2個の球にする

この条件で最終状態を達成できるか?AおよびBは9以下、書かれている数はそれぞれ100以下。

解法

  • 探索…は必要ないです。乗算と余りのない除算のみで構成されるということは、素因数です。素因数の組が等しい…つまり、状態Aの数の積と状態Bの数の積が等しければYesです。
  • 多分、制約は、積がint64に収まるようにってことなんだと思う。

感想

  • 気づきづらい。
  • 本当は「積が等しいかどうか判定せよ」という問題だったけど、がち勢が多かったので難しくしたらしい。
  • おかげで体感300点ぐらいでした…つらいよぅorz