SRM 567 参加記

250

問題文

1 \leq A \leq N, 1 \leq B \leq Mかつ (\sqrt{A} + \sqrt{B}) ^ 2が整数になるような組(A, B)の個数を求めよ。

制約

N, M \leq 77777

考えたこと

  • はじめの5分ほど \sqrt{A ^ 2 + B ^ 2}と勘違いしていた
  • 式を変形すれば \sqrt{A B}が整数であればよいことがわかる
  • つまり平方数
  • Aを固定して考えてみる
  • う〜ん…
  • ABを固定して考えてみる
  • う〜ん…
  • Aを固定してうまくいくアイデアを思いつく
  • S * Aが平方数になるような最小の数Sを求めれば、Bは S n^{2} の形で表せる。
  • Sは素因数分解すればわかる
  • 素因数分解で失敗しないように気をつけて書いた。

500

問題文

長い

考えたこと

  • 手を動かしてみる
  • 各アルファベットの個数だけ考えれば良さそう
  • 表を作ってみる
  • Aがどのアルファベットを先頭に選ぶのがよいか考えてみる
  • 個数がどの文字列にも負けてないなら、その文字を選んで問題無さそう。
  • その文字で勝った相手はそれ以後無視出来る。
  • 貪欲っぽい
  • 選ぶものがなくなるまで置き続けた