โจทย์ข้อนี้ต้องการให้เราตอบคำถามว่าในช่วง ถึง มีกี่ตัวที่มีตัวหาร ตัว โดยมี คำถาม
Preprocessing
สำหรับข้อนี้ขั้นแรกคือ preprocess ว่าแต่ละตัวเลขตั้งแต่ ถึง มีตัวหารกี่ตัว เราสามารถใช้วิธีคล้ายตะแกรงของเอราทอสเทนีส (Sieve of Eratosthenes)
สำหรับทุกจำนวนเต็ม เราจะ initialize จำนวนตัวหาร num_divisors[x] เป็น 0
จากนั้นสำหรับ เราจะเพิ่ม num_divisors[j] สำหรับทุก เพราะ เป็นตัวหารของ
เห็นได้ว่าแต่ละ จะต้องเพิ่ม จำนวน ตัว
int L = 1000000; int num_divisors[1000100]; for (int i = 1; i <= L; i++) for (int j = i; j <= L; j += i) num_divisors[j]++;
ขั้นตอนนี้จึงใช้เวลา
จากนั้นเราจะเก็บทุกตัวใน C[D] โดย C[D] เป็น vector เก็บตัวเลขที่มีตัวหาร ตัว
vector < int > C[510]; for (int i = 1; i <= L; i++) if (num_divisors[i] <= 500) C[num_divisors[i]].push_back(i);
สังเกตว่าการ insert เข้าไปใน vector ในแบบนี้จะทำให้แต่ละ vector เรียงกันจากน้อยไปมาก
ขั้นตอนนี้ใช้เวลา
การตอบ Query
สำหรับ Query เราต้อง Binary Search หาตำแหน่งของค่าน้อยสุดที่ไม่น้อยกว่า ใน C[D] และตำแหน่งของค่าที่น้อยที่สุดที่มากกว่า จากนั้นเมื่อนำมาลบกันจะเป็นคำตอบของคำถาม เราสามารถใช้ Binary Search เพราะข้อมูลใน C[D] เรียงจากน้อยไปมากอยู่แล้ว
การ Binary Search ในแต่ละคำถามใช้เวลา เพราะแต่ละ vector มีขนาดอย่างมาก
หากใช้ภาษา C++ สามารถใช้ std::lower_bound และ std::upper_bound จาก <algorithm> ใน STL สำหรับการ Binary Search ดังกล่าว
for (int i = 1; i <= Q; i++) { int X, Y, D; cin >> X >> Y >> D; auto lb = lower_bound(C[D].begin(), C[D].end(), X); auto ub = upper_bound(C[D].begin(), C[D].end(), Y); cout << int(ub - lb) << "\n"; }
(std::lower_bound(C[D].begin(), C[D].end(), X) จะ return iterator ไปยังตำแหน่งแรกที่ไม่น้อยกว่า ส่วน std::upper_bound(C[D].begin(), C[D].end(), Y) จะ return iterator ไปยังตำแหน่งแรกที่มากกว่า ) 7:51 AM 9/10/2023
ทั้งปัญหานี้จึงใช้เวลา