let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

PBCDIV - Phép chia hết

solution.md

Đầu tiên ta cần có 2 công thức cơ bản:

  • Số số nguyên dương \(x \le n, k \vert x\) là \(\lfloor n / k \rfloor\)
  • Ta đếm số số nguyên chia hết cho cả \(a\) và \(b\) bằng cách đếm số số nguyên chi hết cho bội chung nhỏ nhất của \(a\) và \(b\).

Tiếp theo, có 3 trường hợp cần xét:

  • \[4 \vert x \land 6 \vert x \land 15 \nmid x\]
  • \[6 \vert x \land 15 \vert x \land 4 \nmid x\]
  • \[4 \vert x \land 15 \vert x \land 6 \nmid x\]

Ta loại bỏ trường hợp 3 vì không có số nào thỏa điều kiện này.

Xét trường hợp 1 và 2, vì 2 trường hợp này không giao nhau nên ta có thể xét riêng sau đó cộng kết quả lại.

Xét trường hợp 1: Xét tập hợp các số chia hết cho cả 4 và 6, ta thấy trong tập này có một vài số chia hết cho 15, vì vậy để tính trường hợp 1, ta trừ ra các số chia hết cho cả 4, 6 và 15.

Công thức cho trường hợp 1:

\[F_1(n) = \lfloor n / 12 \rfloor - \lfloor n / 60 \rfloor\]

Tương tự, công thức cho trường hợp 2:

\[F_2(n) = \lfloor n / 30 \rfloor - \lfloor n / 60 \rfloor\]

Tổng 2 trường hợp lại:

\[F(n) = F_1(n) + F_2(n) = \lfloor n / 12 \rfloor + \lfloor n / 30 \rfloor - 2 \lfloor n / 60 \rfloor\]

Kết quả bài toán:

\[F(b) - F(a-1)\]
main.cpp
Open in Github • Download 
#include <iostream>
using namespace std;
#define ll long long

ll count(ll n) {
    return n / 30 + n / 12 - (n / 60) * 2;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        ll a, b;
        cin >> a >> b;
        cout << count(b) - count(a-1) << '\n';
    }
}
Comments