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

1

scratch_huykhanh 9:49 a.m. 19 Tháng 8, 2024

Hint

Số lượng số chia hết cho một trong ba số a, b, c trong đoạn \(1\) -> \(N\) là:
\((\)\(N / a + N / b + N / c) - (N / (lcm(a,b)) + N / lcm(a,c) + N / lcm(b,c)) + N / lcm(a,b,c\)\()\)

0

dpqbao 8:06 p.m. 17 Tháng 8, 2024 ← chỉnh sửa 21 →

bài khó quá tăng tăng thời gian đi ad

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

0

khoa_diep_vien_007 4:10 p.m. 15 Tháng 4, 2022

hình như bài này phải có công thức để giải quyết mà ko bt làm như nào huhu

2 phản hồi