[Codeforces] Codeforces Round #726 (Div. 2) D. Deleting Divisors
問題
方針
\( n \) が奇数であるとき
\( n \) が素数であるとき Bob の勝利は自明です.\( n \) が素数でないとき, \( n \) の約数の中から奇数 \( p \) を選んだとき,奇数 \( q \) を用いて,\( n = pq \) と表すことができるので,
\[ n -p= p(q-1)\]
となり,\( n-p\) は \( 1 \) 以外の奇数の約数を持つ偶数となります.
\( n \) が \( 1 \) 以外の奇数の約数を持つ偶数であるとき
このとき \( n \) は奇数 \( p \) と自然数 \( m \) を用いて,\( n = 2^{m}p \) と表すことができます.ここで,\( p \) を選んだとすると,
\[ n-p=p(2^m -1)\]
となり,\( n-p\) は奇数となります.
\( n \) が \( 1 \) 以外の奇数の約数を持たない偶数であるとき
このとき \( n \) は自然数 \( m \) を用いて,\( n = 2^m \) と表すことができます.約数として,\( 2^{m-1} \) を選んだとき,
\[ n-2^{m-1} = 2^{m-1}\]
となり,その他の約数を選んだとすると,自然数 \( k \neq m-1\) を用いて,
\[ n-2^{k} = 2^{k}(2^{m-k}-1)\]
となります.
ここで,\( n \) が奇数である状態を \( S_1 \),\( n \) が \( 1 \) 以外の奇数の約数を持つ偶数である状態を \( S_2 \),\( n \) が \( 1 \) 以外の奇数の約数を持たない偶数である状態を \(S_3 \) とします.\( S_1 \) から遷移できないときは,現在の数が素数であるときであり,\(S_3\) から遷移できないときは,現在の数が \( 2 \) であるときです.また,当たり前ですが \( S_2 \) から遷移できないことはありません.
\( S_1 \) からの遷移は \( S_2 \) のみであり,\( S_2 \) からの遷移は \( S_1 \) を選ぶことができるので,\( n \) が奇数のときは Bob が勝ちます.同様に,\( S_2 \) からの遷移は \( S_1 \) を選ぶことができるので \( n \) が \( 1 \) 以外の奇数の約数を持つ偶数であるとき Alice が勝ちます.\( S_3 \) からの遷移は,\(S_2 \) または \(S_3 \) となりますが,\(S_2\) に遷移したときは Alice の負けとなるので,\( S_3 \) の遷移を選びます.Bob も同様に \(S_3 \) の遷移を選びます.したがって,\( m \) を自然数として,\( n = 2^m \) と表した時,\( m -1 \) 回 \( S_3 \) への遷移が起きることが可能なので,\( m \) が偶数のときは Alice が勝ち,偶数のときは Bob が勝ちます.
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll n; void solve() { if (n % 2 == 1) { cout << "Bob\n"; return; } ll k = 2; int cnt = 1; while (k < n) { k *= 2; cnt++; } if (k == n && cnt % 2 == 1) { cout << "Bob\n"; } else { cout << "Alice\n"; } } int main() { int t; cin >> t; for (int i = 0; i < t; i++) { cin >> n; solve(); } return 0; }
感想
解説を読んでなんとなく分かりました.
ディスカッション
コメント一覧
まだ、コメントがありません