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