Editorial for Chia hết 2

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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