スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Codeforces Round #166 (Div. 2) E : Three Horses

自然数のペアを (x, y) などと書く。

最初、(x, y) だけを持っている。
次の操作を好きなだけ施してよい。
操作 1 : (a, b) があるとき (a+1, b+1) を新たにもらえる
操作 2 : (2a, 2b) があるとき (a, b) を新たにもらえる
操作 3 : (a, b) と (b, c) があるとき (a, c) を新たにもらえる

このようにしてできる自然数のペアの集合を S(x, y) と書く。

自然数の列 a_1, a_2, ..., a_n が与えられる。
(1, a_i) ∈ S(x, y) ( i = 1, 2, ..., n )
となるような (x, y) ( 1 ≦ x < y ≦ m ) はいくつあるか?

・ 1 ≦ n ≦ 10^5
・ 2 ≦ m, a_i ≦ 10^9

解答

Editorial を読んだ ( けど結果だけしか書かれていなかったので自分で補完した )。

まず、色々さわってみてどんなペアが作れるのかを調べてみる。

(a, b) からはじめる。
操作 1 を a-2 回施して (2a-2, a+b-2) ができる。
操作 1 を b-2 回施して (a+b-2, 2b-2) ができる。
(2a-2, a+b-2) と (a+b-2, 2b-2) に操作 3 を施して (2a-2, 2b-2) ができる。
操作 2 を施して (a-1, b-1) ができる。

よって、(a, b) から (a+k, b+k) ( k は整数, ただし a+k ≧ 1 ) が作れることになる。
これはつまり S(a,b) = S(a+k, b+k) ということで、b-a の値が等しいペアはどれからはじめても同じ結果になることがわかる。
そこで d = b-a とおいて (1, 1+d) の形にだけ注目することにする。

次は (1, 1+d) からはじめる。
操作 1 を施して (2, 2+d) ができる。
d が偶数なら、操作 2 を施して (1, 1+d/2) ができる。
操作 1 を施して (2, 2+d/2) ができる。
d/2 が偶数なら、操作 2 を施して (1, 1+d/4) ができる。
……
このようにして、(1, 1+d) から (1, 1+d') ( d = 2^e・d', d' は奇数 ) を作ることができる

(1, 1+d') からはじめる。
操作 1 を d' 回施して (1+d', 1+2d') ができる。
(1, 1+d') と (1+d', 1+2d') に操作 3 を施して (1, 1+2d') ができる。
操作 1 を d' 回施して (1+d', 1+3d') ができる。
(1, 1+d') と (1+d', 1+3d') に操作 3 を施して (1, 1+3d') ができる。
……
このようにして、(1, 1+d') から (1, 1+kd') ( k は自然数 ) を作ることができる

以上のことから、y-x = d = 2^e・d' とおくと
S(x, y) は (1, 1+kd') ( k は自然数 ) を含むことが分かった。

実は、(1, 1+○) の形のペアで S(x, y) に含まれるものはこれですべて。
証明はちょっと考えたくらいでは思いつかなかったけど、さわってみた感じだとこれ以上どうしようもない気はする。

この結果から、元々解きたかった問題の n = 1 のときの答えがわかったことになる。
つまり、(x, y) が (1, a_1) ∈ S(x, y) をみたすための必要十分条件は d' が a_1-1 の約数であること

ここまでわかればあとは簡単で、一般の n については
(x, y) が問題の条件をみたす ⇔ d' が a_1-1, a_2-1, ..., a_n-1 の公約数である
となる。

なので、ありうる d' の値は GCD(a_1-1, a_2-1, ..., a_n-1) の奇数の約数であり、各 d' を ×2, ×4, ... していくことでありうる d の値を全て求められる。
最後に、1 ≦ x < y ≦ m に注意して、ありうる (x, y) の値の個数を勘定すればいい。

ソースコード

http://www.codeforces.com/contest/271/submission/3108323
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。