The Cat in the Hat

ACM

http://acm.uva.es/p/v1/107.html
問題の設定は結構ややこしくて

  1. ネコが頭上に、身長が自分の1/(n+1)の小さなネコをn匹乗せている。
  2. 身長が1のネコは何も乗せていない。身長1のネコだけが働く。
  3. 再下段のネコの身長と、身長1のネコの数が与えられている。nは秘密。

ここで、働いていないネコの数とすべてのネコの身長の合計を求めろと言うんだけど、意味わかりませんね。数式で言うとこういうことです。

  1. xyと(x-1)yが与えられる。
  2. xとyを求め、\sum^{y-1}_{i=0}(x-1)^iと\sum^{y}_{i=0}(x-1)^ix^{y-i}を求めろ。

素因数分解かけて(x-1)の候補を出して、x^yに一致するか確かめれば一発じゃん、とやってみたらWrong Answer。どうして間違いなのかわからずに、結局ここにあった一言で解決。

ただし、 2k と 1 の入力ペアについても、その処理を忘れないように。

http://bal4u.dip.jp/mt/program/archives/2004/11/107_the_cat_in.html
ああああそうだったぁ。これだからもうおいらってば！
ちなみに、作ったプログラム29kbのうち、28kbまでが素因数分解のための素数のテーブル。