[Codeforces] Codeforces Round #726 (Div. 2) D. Deleting Divisors

2021年6月19日

問題

Problem - 1537D - Codeforces

Codeforces. Programming competitions and contests, programming community

https://codeforces.com/problemset/problem/1537/D

方針

\( 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;
}