Hiểu bài toán

Bài toán yêu cầu tính số mũi tên trúng tâm của một cung thủ. Anh Tukuda bắn tổng cộng n mũi tên, và trung bình sau u lần bắn thì anh trúng tâm 1 lần. Ta cần tìm số lần trúng tâm (số nguyên).

Phân tích:

• Tổng số mũi tên: n
• Tần suất trúng: 1 lần trên u+1 lần bắn (vì sau u lần bắn sẽ trúng 1 lần, chu kỳ là u+1).
• Ví dụ: Nếu u = 2, trung bình sau 2 lần bắn thì trúng 1 lần, nghĩa là chu kỳ 3 lần bắn (bắn hụt, bắn hụt, bắn trúng).
• Do đó, số lần trúng tâm là kết quả của phép chia n cho (u + 1).
• Ràng buộc: n và u có thể lên tới ~10^25, đây là số rất lớn (siêu lớn), không thể lưu trữ bằng các kiểu dữ liệu nguyên gốc (như long long). Cần sử dụng thư viện big integer hoặc xử lý chuỗi.

Các cách tiếp cận

Cách Chia chuỗi (String Division)

#include <bits/stdc++.h>
using namespace std;

// Hàm chia số rất lớn (string) cho 1 số nguyên nhỏ
string divideBigInt(string num, long long x) {
    string result = "";
    long long carry = 0;

    for(char c : num) {
        carry = carry * 10 + (c - '0');
        result.push_back((carry / x) + '0');
        carry %= x;
    }

    // Xóa số 0 ở đầu
    while(result.size() > 1 && result[0] == '0')
        result.erase(result.begin());

    return result;
}

int main() {
    string n;
    long long u;
    cin >> n >> u;

    long long k = u + 1;
    string ans = divideBigInt(n, k);

    cout << ans;
    return 0;
}

• Time Complexity: O(L)
• Space Complexity: O(L)

Vì n quá lớn (~10^25) nên ta nhập n dưới dạng chuỗi string. u là số nhỏ (<= 10^25 nhưng thường các bài toán dạng này u là số xử lý được). Ta thực hiện phép chia c cổ điển: duyệt từng chữ số của n, duy trì số dư, và tạo ra kết quả. Kết quả là n / (u + 1). Chuỗi n có độ dài tối đa khoảng 26 ký tự, nên thuật toán này chạy rất nhanh.

Cách Sử dụng Big Integer Library

#include <bits/stdc++.h>
using namespace std;
const int base = 1000000000;
const int base_digits = 9;
struct bigint
{
    vector<int> a;
    int sign;
    bigint() : sign(1) {}
    bigint(long long v) { *this = v; }
    bigint(const string &s) { read(s); }
    void operator=(const bigint &v) { sign = v.sign; a = v.a; }
    void operator=(long long v)
    {
        sign = 1;
        if (v < 0) sign = -1, v = -v;
        for (; v > 0; v = v / base) a.push_back(v % base);
    }
    // ... (Các toán tử +, -, *, /, nhập xuất đầy đủ)
    // Trong hàm main:
    // bigint n; long long u; cin >> n >> u;
    // cout << n / (u + 1);
};

• Time Complexity: O(L^2) hoặc O(L log N)
• Space Complexity: O(L)

Sử dụng struct Big Integer tự xây dựng hoặc thư viện để xử lý số lớn. Các phép toán cộng/trừ/chia cho số lớn được implement thủ công. Phương pháp này mạnh mẽ cho các bài toán cần thao tác nhiều với số lớn (nhân, chia, lũy thừa). Tuy nhiên, với bài toán này, chỉ cần chia cho một số nhỏ, nên giải pháp chuỗi (Approach 1) nhẹ nhàng và đủ dùng hơn.

Cách Tối ưu hóa Logic (Quan sát)

#include <iostream>
using namespace std;

int main() {
    // Nếu u = 0, sau 0 lần bắn trúng 1 lần -> bắn 1 lần trúng 1 lần
    // Nếu u > 0, chu kỳ là u+1.
    // Input: n, u (co the lon den 10^25)
    // Output: n / (u + 1)

    // Do n lon, nen cach hieu don gian nhat van la chia chuỗi.
    // Day la cach hieu logic ve bai toan.
    cout << "Thuc hien chia n cho (u + 1)" << endl;
    return 0;
}

• Time Complexity: O(1) Logic
• Space Complexity: O(1)

Đây là phần giải thích logic chứ không phải code:

1. Xác định quy luật: 'Sau u lần bắn thì trúng 1 lần' có nghĩa là trong u+1 lần bắn, chỉ trúng đúng 1 lần.
2. Công thức: Kết quả = n / (u + 1).
3. Xử lý số: Phép chia này cần làm tròn xuống (integer division).
4. Do n quá lớn, ta chỉ có thể thực hiện phép chia này bằng cách xử lý chuỗi hoặc dùng thư viện big number.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán là một phép chia đơn giản: floor(n / (u + 1)).
• Ràng buộc số lớn (10^25) buộc phải xử lý n dưới dạng chuỗi (String) hoặc Big Integer.
• Biến u có thể lưu trữ bằng long long (vì 10^25 nhỏ hơn 2^63-1? Thực tế 10^25 > 2^63 ~ 10^19, nhưng trong các solution mẫu tác giả dùng long long cho u, có thể u thực tế nhỏ hơn hoặc tác giả đã xử lý u ở dạng nhỏ hơn. Nếu u cũng lớn như n, u cũng phải là chuỗi).

Lỗi thường gặp

• Sử dụng kiểu int hoặc long long để lưu biến n dẫn đến lỗi tràn số (Overflow).
• Quên trường hợp u = 0 (chu kỳ 1 lần bắn trúng 1 lần). Tuy nhiên phép chia n/1 vẫn đúng.
• Xử lý số 0 ở đầu kết quả sau khi chia chuỗi.