[Codeforces] Global Round 1 C. Meaningless Operations

Meaningless Operations

https://codeforces.com/contest/1110/problem/C

考え方

題意

\( f(b) = gcd(a \ \mathrm{XOR} \ b,\ a\ \mathrm{AND} \ b) \ (0 < b < a)\) の最大値を答えます。

方針

解説を読みました。

\( a \leq 2^x – 1\) を満たす最小の \( x \) とします。

\( a \neq 2^x – 1\) のとき

\( b = (2^x – 1) \ \mathrm{XOR} \ a \) は最上位のビットが \( 0 \) であるので、\( a \) より小さいことが言えます。

このとき、\( a \ \mathrm{XOR} \ b  = 2^x – 1\)、\( a \ \mathrm{AND} \ b  = 0\) なので、\( 2^x – 1\) が最大値となります。

\( a = 2^x – 1\) のとき

\( a \ \mathrm{XOR} \ b  = a – b \) 、\( a \ \mathrm{AND} \ b  = b \) となります。

\( gcd(x, x + y) = gcd(x, y)\) が成り立つので、\(gcd(a – b, b) = gcd(a, b) \) となります。なので、\( a \) の \(a \) 未満の約数の最大値が答えとなります。

コード

感想

最大値を取る証明ができていないので、良く分かりませんでした。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする