DIVISIBLE

Tác giả:

Dạng bài

Điểm: 100 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một số nguyên không âm \(x\) được gọi là đẹp nếu \(x\) chia hết một trong ba số \(4, 7, 11\). Hãy tìm số lượng số đẹp nằm trong khoảng \([L; R]\)

Dữ liệu

Dòng đầu chứa \(t\) không quá \(1000\) - số câu hỏi
\(t\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(L, R\) \((L < R)\)

Kết quả

Kết quả thỏa mãn yêu cầu đề bài ứng với mỗi câu hỏi.

Sample input

2
1 10
11 15

Sample output

3
3

Ràng buộc

50% test có \(0 \le L < R \le 10^{6}\)
50% test có \(0 \le L < R \le 10^{12}\)

Bình luận

Gợi ý: sử dụng công thức đếm số lượng số chia hết cho k từ a->b
Code C++:

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
int left(int l, int k)
{
    if (l%k==0) return l;  else return l/k*k+k;
}
int right(int r, int k) {return r/k*k;}
int am(int l, int r, int k)
{
    if (l>r) swap(l,r);
    int l1,r1; l1=left(l,k); r1=right(r,k);
    return (r1-l1)/k+1;
}
int c(int l, int r)
{
    if (l>r) swap(l,r); int kq=0;
    kq=kq+am(l,r,4)+am(l,r,7)+am(l,r,11);
    kq=kq-am(l,r,28)-am(l,r,44)-am(l,r,77);
    kq=kq+am(l,r,308);
    return kq;
}
signed main()
{
    int n,l,r; cin>>n; while (n--)
    {
        cin>>l>>r;  cout<<c(l,r)<<endl;
    }
}

3 bình luận nữa