TS10 Đắk Lắk 2026 - Bài 3

Xem dạng PDF

Gửi bài giải

Điểm: 11,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Trong buổi học chuyên đề về số học, thầy giáo đưa ra khái niệm số đặc biệt: một số nguyên dương ~x~ gọi là số đặc biệt nếu tổng các ước nguyên dương của ~x~ chia hết cho ~3~.

Ví dụ: ~15~ là một số đặc biệt vì tổng các ước của ~15~ là ~1+3+5+15=24~ chia hết cho ~3~; ~12~ không phải số đặc biệt vì tổng các ước của ~12~ là ~1+2+3+4+6+12=28~ không chia hết cho ~3~.

Cho trước một dãy số có ~n~ số nguyên dương ~a_1,a_2,\dots,a_n~, thầy đưa ra ~q~ câu hỏi có dạng ~l,r,k~ với ý nghĩa số lượng số đặc biệt trong dãy con ~a_l,a_{l+1},\dots,a_r~ ~(1 \le l \le r \le n)~ có lớn hơn hoặc bằng ~k~ hay không, nếu có thì trả lời "YES", ngược lại trả lời "NO". Thầy yêu cầu cả lớp lập trình trả lời ~q~ câu hỏi trên.

Yêu cầu: Hãy viết chương trình trả lời ~q~ câu hỏi của thầy giáo.

Input

  • Dòng thứ nhất chứa hai số nguyên dương ~n,q~ ~(2 \le n,q \le 10^5)~;

  • Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,\dots,a_n~ ~(a_i \le 10^5, 1 \le i \le n)~;

  • ~q~ dòng tiếp theo, mỗi dòng gồm ba số nguyên dương ~l,r,k~ ~(1 \le l \le r \le n, 1 \le k \le 10^5)~.

Các số trên một dòng cách nhau một khoảng trắng.

Output

Gồm ~q~ dòng trả lời tương ứng cho ~q~ câu hỏi của thầy giáo.

Scoring

Subtask Điểm Ràng buộc
1 ~50\%~ ~n,q \le 10^3~
2 ~50\%~ Không có ràng buộc gì thêm

Sample Input 1

5 3
19 8 3 17 18
2 5 3
4 4 1
3 3 1

Sample Output 1

YES
YES
NO

Notes

Với trường hợp ~l=2,r=5~, dãy con ~\{8;3;17;18\}~, tổng các ước của ~8~ là ~1+2+4+8=15~, tổng các ước của ~3~ là ~1+3=4~, tổng các ước của ~17~ là ~1+17=18~, tổng các ước của ~18~ là ~1+2+3+6+9+18=39~. Có ~3~ số đặc biệt là ~8;17;18~ vì mỗi số đều có tổng các ước chia hết cho ~3~, với ~k=3~ nên kết quả là "YES".


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 0
    missmphuog  đã bình luận lúc 29, Tháng 10, 2026, 9:43
    
    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    
    const int N = 100000;
    int tong[N + 1];
    int a[N + 1], pre[N + 1];
    
    void sang() {
        for (int i = 1; i <= N; i++) {
            for (int j = i; j <= N; j += i) {
                tong[j] += i;
            }
        }
    }
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(NULL);
    
        // freopen("BAI3.INP", "r", stdin);
        // freopen("BAI3.OUT", "w", stdout);
    
        sang();
    
        int n, q;
        cin >> n >> q;
    
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
    
            pre[i] = pre[i - 1];
    
            if (tong[a[i]] % 3 == 0) {
                pre[i]++;
            }
        }
    
        while (q--) {
            int l, r, k;
            cin >> l >> r >> k;
    
            int dem = pre[r] - pre[l - 1];
    
            if (dem >= k)
                cout << "YES\n";
            else
                cout << "NO\n";
        }
    
        return 0;
    }