Hướng dẫn giải của Chia hết 2

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Chia hết 2

  • Xuất phát từ bài toán: Có bao nhiêu số tự nhiên không quá ~N~, chia hết cho ~K~? Đáp án: ~res = [N/K] + 1~ với kí hiệu [X] là phần nguyên của X.
  • Suy ra số lượng số tự nhiên trong đoạn ~[L, R]~ chia hết cho ~K~ là: ~[R/K] - [(L-1)/K]~.
  • Vậy với bài toán này, đếm số lượng số tự nhiên có ~N~ chữ số mà chia hết cho ~2^X~ ta làm như sau:
    • Số ~A~ có ~N~ chữ số tức là ~A~ thuộc đoạn ~[L, R] = [10^{N-1}, 10^N - 1]~.
    • Tính ~K = 2^X~.
    • Kết quả: ~res = R / K - (L-1) / K~
Code tham khảo
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    cin.tie(0)->sync_with_stdio(0);
    freopen("CHIAHET2.INP", "r", stdin);
    freopen("CHIAHET2.OUT", "w", stdout);
    int q;
    cin >> q;
    while(q--) {
        int n, x;
        cin >> n >> x;
        ll t = 1;
        for (int i = 1; i < n; i++) {
            t *= 10;
        }
        ll div = (1ll << x); // 2^x
        ll left = (t - 1) / div;
        ll r = t * 10 - 1;
        ll right = r / div;
        if (n == 1) right++;
        cout << right - left << '\n';
    }
    return 0;
}