読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 537 Div2

TopCoder

o--
877897
まるで成長が見られない

250

ある国では、王子様の名前の決め方には掟がある。それは以下のようなものである。

  • すべての文字が小文字のアルファベットで、8文字ちょうどであること
  • 母音が2文字、子音が6文字であること
  • 2つの母音は同じ文字であること

名前が文字列として与えられるので、大丈夫で問題ないなら"YES"を、一番いいのを頼む時には"NO"を返せ。


文字が小文字かどうかの判定を忘れていたが、
Each character of name will be one of 'a'-'z'.
という奇跡が起こる。

550

とあるアヒルの王国の通貨体型は、私たちのそれとは異質のものである。

価値Aの通貨と価値Bの通貨のみで取引が行われており(A, B は正の整数)、すべての商品の値段は、その2つの通貨で表すことができる値段になっている。(すなわち、非負の整数p,qを用いると A * p + B * q で表せる)

アヒルの王国の王様は、この通貨体型に飽きてきた。そこで、新たに X, Y の2種類の通貨に切り替えることにしたが、Xの値はエライ人が決めてくれた。

A, B で表すことのできた値段をすべて表すことのできるX, Yは何種類あるだろうか。条件に当てはまるYの個数を求めよ。


愚直に (A%X==0 && B%Y==0) || (A%Y==0 && B%X==0) で調べれば良い。
A * p + B * q が出てきた時点で「拡張ユークリッド法」とか「互いに素」という言葉が思いついたのは良かったかもしれない。
でも、A, B, X <= 200 という制約から O(ABX) のアルゴリズムなら通るんじゃ? と思いつくことのほうが重要でしょう。