# Tổng hợp một số bài toán - Kho đề

## Bài toán 1: Trò chơi với phép nhân - GS.PVH

### Đề bài

#### Đặt vấn đề

Cho một số nguyên dương $n$. Hai người $A$ và $B$ chơi một trò chơi như sau: Ban đầu có số $t = 1$. Đến lượt của mình, mỗi người nhân $t$ cho một số nguyên dương từ $2$ đến $9$, sao cho $t \le n$ sau khi nhân. Nếu ai không thực hiện được lượt chơi của mình, người đó sẽ thua. Xác định người thắng trong trò chơi này nếu cả hai cùng chơi tối ưu.

#### Đầu vào

- Dòng đầu tiên là số truy vấn $Q$.
- $Q$ dòng tiếp theo, mỗi dòng là một số nguyên dương $n$, mô tả một ván đấu.

#### Đầu ra
- Gồm $Q$ dòng, mỗi dòng là kết quả của ván đấu nếu cả hai chơi tối ưu - In ra `A` nếu $A$ thắng và `B` nếu $B$ thắng.

#### Giới hạn cố định
- $Q \le 10^4$.
- $n \le 10^{18}$.

#### Chia điểm
- $20\%$ số điểm có $Q \le 100, n \le 10^5$.
- $20\%$ số điểm có $Q \le 10^4, n \le 10^5$.
- $20\%$ số điểm có $Q \le 100, n \le 10^9$.
- $20\%$ số điểm có $Q \le 10^4, n \le 10^9$.
- $20\%$ số điểm không có giới hạn gì thêm.

#### Ví dụ
- Input:

    3
    9 18 27

- Output:

    A
    B
    A

### Lời giải

Ta có thể biểu diễn bất kỳ trạng thái $t$ nào dưới dạng $2^a \times 3^b \times 5^c \times 7^d$. Do đó, ta có thể đặt $dp[a][b][c][d]$ biểu diễn kết quả của trò chơi với $t$ hiện tại bằng $2^a \times 3^b \times 5^c \times 7^d$.

Hiển nhiên, kết quả trò chơi là $B$ thắng khi $2^a \times 3^b \times 5^c \times 7^d \ge n$. Do đó $dp[a][b][c][d]$ trong trường hợp này cho kết quả $B$ thắng.

Sử dụng đệ quy có nhớ để tiếp tục giải quyết với các $t$ nhỏ hơn.

Lưu ý cần xử lý chính xác các trường hợp đầu tiên (trường hợp $2^a \times 3^b \times 5^c \times 7^d \ge n$).

Độ phức tạp: $O(Q \times log^4(n))$.

### Mã nguồn

<chưa có>

Subtask 4:

#pragma GCC optimize("O3,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,sse4,avx,avx2,fma,bmi,bmi2,abm")
#include<bits/stdc++.h>
using namespace std;

unordered_map<int, int>dp;

int get_dp(int u)
{
    if(dp[u] != 0) return dp[u];
    int ans = -1;
    for(int i = 2; i <= 9; i ++)
        ans = max(ans, -get_dp((u - 1) / i + 1));
    dp[u] = ans;
    return ans;
}

void test()
{
    int n;
    cin >> n;
    if(get_dp(n) == -1) cout << "A\n";
    else cout << "B\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    dp[1] = -1;
    long long t;
    cin >> t;
    while(t --) test();
}