Đếm số chia hết

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
cuom1999
Dạng bài
Điểm: 300 Thời gian: 3.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho \(n\) số tự nhiên \(a_1, a_2, ..., a_n\). Hãy xác định xem có bao nhiêu số \(x\) trong đoạn \([l, r]\) mà \(x\) không chia hết cho số \(a_i\) nào cả.

Input

  • Dòng đầu tiên chứa 3 số nguyên dương \(n, l, r \ (1 \leq n \leq 18)\)
  • Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, ..., a_n \ (1 \leq a_i \leq 10^9)\)

Output

  • In ra một số nguyên là đáp số bài toán

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(1 \leq l \leq r \leq 10^6\)
  • Subtask \(2\) (\(70\%\) số điểm): \(1 \leq l \leq r \leq 10^{18}\)

Example

Test 1

Input 
3 10 20
3 4 5
Output 
5

Bình luận


  • 4
    longkold00    4:31 p.m. 21 Tháng 10, 2021

    Để làm đc bài này, chúng ta cần đọc qua định lý bao hàm loại trừ link mình để ở đây
    . Như vậy chúng ta sẽ tính số số chia hết cho bất kì số nào trong mảng a[] r trừ đi là xong.

    1. Số số cần tìm sẽ = res. Gọi Ki là số số thuộc [l,r] chia hết cho bội chung nn của i số bất kì trong
      a[], như vậy theo định lý ta sẽ có res= K1 - K2 + K3 - K4 + K5 - K6 +...

    2. ta sẽ sort các số trong mảng a[] để tiện cho việc giảm độ phức tạp khi đệ quy

    3. sử dụng vector x(1e7,1) để tạo bội chung nhỏ nhất tại vị trí đệ quy x[i]

    4. Ta sẽ đệ quy như sau:

      void loading(ll i, ll choice)
      {

    // ta khởi đầu với i=1 và choice=0 thể hiện chọn lần 1 và duyệt qua n phần tử 

    FOR(j,choice+1,n,1) 
{
    ll uoc=__gcd(x[i-1],a[j]);

    x[i]=1LL*x[i-1]*a[j]/uoc;

    ll k=r/x[i]-(l+x[i]-1)/x[i]+1;

    if(i%2==1)  res+=k;     
    else res-=k;

    if(j+1<=n && a[j+1]/(__gcd(x[i],a[j+1]))<=(r/x[i])) // ta sẽ dừng đệ quy và hạn chế số lớn nếu bcnn tiếp theo > r 
    loading(i+1,j);     
}

    }

      • 4 bình luận nữa