Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Ước chung lớn nhất trên đoạn

    Cho dãy số nguyên dương a1,…,ana_1, \dots, a_na1​,…,an​. Với mỗi truy vấn (l,r)(l, r)(l,r), hãy tính gcd⁡(al,al+1,…,ar)\gcd(a_l, a_{l+1}, \dots, a_r)gcd(al​,al+1​,…,ar​) — ước chung lớn nhất của các phần tử trong đoạn.

    Vì GCD là phép toán idempotent (gcd⁡(x,x)=x\gcd(x,x)=xgcd(x,x)=x), ta có thể dùng bảng thưa (sparse table) để trả lời mỗi truy vấn trong O(1)O(1)O(1) sau tiền xử lý O(nlog⁡n)O(n\log n)O(nlogn).

    • Định dạng đầu vào:

      Dòng đầu chứa nnn và qqq. Dòng thứ hai chứa nnn số nguyên dương. qqq dòng tiếp theo, mỗi dòng hai số l rl\ rl r.

    • Ràng buộc đầu vào:

      1≤n,q≤2⋅1051 \le n, q \le 2\cdot10^51≤n,q≤2⋅105, 1≤ai≤1091 \le a_i \le 10^91≤ai​≤109, 1≤l≤r≤n1 \le l \le r \le n1≤l≤r≤n.

    • Định dạng đầu ra:

      Với mỗi truy vấn, in gcd⁡\gcdgcd tương ứng trên một dòng.

    Ví dụ:

    Đầu vào:

    4 2
12 18 6 30
1 2
1 4

    Đầu ra:

    6
6

    Giải thích:

    gcd(12,18) = 6. gcd của toàn dãy 12,18,6,30 cũng bằng 6 vì 6 chia hết mọi phần tử và không số lớn hơn nào làm được điều đó.

    Đang tải editor...