chúc ae ac Bob đang bị dương tính với COVID-19, và ở nhà cậu ấy chẳng có gì để làm nên Bob muốn chơi một trò chơi gì đấy để cho cậu ấy đỡ chán. Bob nhớ ra là c
chúc ae ac Bob đang bị dương tính với COVID-19, và ở nhà cậu ấy chẳng có gì để làm nên Bob muốn chơi một trò chơi gì đấy để cho cậu ấy đỡ chán. Bob nhớ ra là cậu ấy có 1 chiếc hộp thần kỳ bao gồm vô số các số từ đến . Bob lấy số trong chiếc hộp đấy ra và đặtlên trên một chiếc bàn. Nhận ra rằng chơi một mình thì chẳng có gì vui nên Bob rủ Alice chơi cùng. Trong khi Bob không biết rằng mình sẽ phải làm gì với số trên bàn, Alice có một ý tưởng: Vì Alice không thể chơi cùng Bob trực tiếp vì tình hình dịch bệnh phức tạp, Alice sẽ có câu hỏi cho Bob trả lời. Với mỗi câu hỏi, Bob sẽ phải lấy ra các số ở vị trí từ đến , sau đó tìm ước chung lớn nhất của các số còn lại trên bàn. Sau mỗi câu hỏi, Bob sẽ đặt lại các số vừa lấy về vị trí ban đầu. Yêu cầu: Hãy giúp Bob trả lời câu hỏi mà Alice đã cho. Dữ liệu Dòng đầu tiên chứa hai số nguyên dương và là số lượng số trên bàn và số câu hỏi Alice dành cho Bob (). Dòng tiếp theo chứa số nguyên dương là các số ở trên bàn (). dòng tiếp theo, mỗi dòng chứa hai số nguyên và (). Kết quả In ra dòng, mỗi dòng là đáp án của câu hỏi thứ mà Alice dành cho Bob (). Ví dụ Input Copy 3 3 2 6 9 1 1 2 2 2 3 Output Copy 3 1 2
Lời giải 1 :
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
struct Segment_tree {
int f[N * 4], n;
vector<int> arr;
void build(int l, int r, int id) {
if (l == r) {
f[id] = arr[l - 1]; return;
}
int mid = (l + r) >> 1, k = id << 1;
build(l, mid, k);
build(mid + 1, r, k | 1);
f[id] = gcd(f[k], f[k | 1]);
}
int get(int u, int v, int l, int r, int id) {
if (r < u || v < l) return 0;
if (u <= l && r <= v) return f[id];
int mid = (l + r) >> 1, k = id << 1;
return gcd(get(u, v, l, mid, k), get(u, v, mid + 1, r, k | 1));
}
int get(int u, int v) {
return get(u, v, 1, n, 1);
}
int query(int u, int v) {
return gcd(get(1, --u), get(++v, n));
}
} St;
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, Q;
cin >> n >> Q;
vector<int> a(n);
for (int &x: a) cin >> x;
St.n = n;
St.arr = a;
St.build(1, n, 1);
while (Q--) {
int u, v;
cin >> u >> v;
cout << St.query(u, v) << "\n";
}
}
Thảo luận
Có thể bạn quan tâm
Bạn có biết?
Tin học, tiếng Anh: informatics, tiếng Pháp: informatique, là một ngành khoa học chuyên nghiên cứu quá trình tự động hóa việc tổ chức, lưu trữ, xử lý và truyền dẫn thông tin của một hệ thống máy tính cụ thể hoặc trừu tượng (ảo). Với cách hiểu hiện nay, tin học bao hàm tất cả các nghiên cứu và kỹ thuật có liên quan đến việc mô phỏng, biến đổi và tái tạo thông tin.
Nguồn : Wikipedia - Bách khoa toàn thưTâm sự 11
Lớp 11 - Năm thứ hai ở cấp trung học phổ thông, gần đến năm cuối cấp nên học tập là nhiệm vụ quan trọng nhất. Nghe nhiều đến định hướng sau này rồi học đại học. Ôi nhiều lúc thật là sợ, hoang mang nhưng các em hãy tự tin và tìm dần điều mà mình muốn là trong tương lai nhé!
Nguồn : ADMIN :))Xem thêm tại https://loigiaisgk.com/cau-hoi or https://giaibtsgk.com/cau-hoi
Copyright © 2021 HOCTAPSGK