โจทย์ข้อนี้ต้องการให้เราตอบคำถามว่าในช่วง $X$ ถึง $Y$ มีกี่ตัวที่มีตัวหาร $D$ ตัว โดยมี $Q$ คำถาม

$(1\leq X \leq Y \leq 1000000, D \leq 500, Q \leq 100)$

Preprocessing

สำหรับข้อนี้ขั้นแรกคือ preprocess ว่าแต่ละตัวเลขตั้งแต่ $1$ ถึง $L=1000000$ มีตัวหารกี่ตัว เราสามารถใช้วิธีคล้ายตะแกรงของเอราทอสเทนีส (Sieve of Eratosthenes)

สำหรับทุกจำนวนเต็ม $x$ เราจะ initialize จำนวนตัวหาร num_divisors[x] เป็น 0

จากนั้นสำหรับ $1 \leq i \leq L$ เราจะเพิ่ม num_divisors[j] สำหรับทุก $j = i, 2i, 3i, \dots (j \leq L)$ เพราะ $i$ เป็นตัวหารของ $j$

เห็นได้ว่าแต่ละ $i$ จะต้องเพิ่ม $j$ จำนวน $\frac{L}{i}$ ตัว

  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]++;

ขั้นตอนนี้จึงใช้เวลา $\frac{L}{1} + \frac{L}{2} + \frac{L}{3} + \dots + \frac{L}{L} = \mathcal{O}(L \log{} L)$

จากนั้นเราจะเก็บทุกตัวใน C[D] โดย C[D] เป็น vector เก็บตัวเลขที่มีตัวหาร $D$ ตัว

  vector < int > C[510];
  for (int i = 1; i <= L; i++)
    if (num_divisors[i] <= 500)
      C[num_divisors[i]].push_back(i);

สังเกตว่าการ insert $i$ เข้าไปใน vector ในแบบนี้จะทำให้แต่ละ vector เรียงกันจากน้อยไปมาก

ขั้นตอนนี้ใช้เวลา $\mathcal{O}(L)$

การตอบ Query

สำหรับ Query $X, Y, D$ เราต้อง Binary Search หาตำแหน่งของค่าน้อยสุดที่ไม่น้อยกว่า $X$ ใน C[D] และตำแหน่งของค่าที่น้อยที่สุดที่มากกว่า $Y$ จากนั้นเมื่อนำมาลบกันจะเป็นคำตอบของคำถาม เราสามารถใช้ Binary Search เพราะข้อมูลใน C[D] เรียงจากน้อยไปมากอยู่แล้ว

การ Binary Search ในแต่ละคำถามใช้เวลา $\mathcal{O}(\log{} L)$ เพราะแต่ละ vector มีขนาดอย่างมาก $L$

หากใช้ภาษา 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 ไปยังตำแหน่งแรกที่ไม่น้อยกว่า $X$ ส่วน std::upper_bound(C[D].begin(), C[D].end(), Y) จะ return iterator ไปยังตำแหน่งแรกที่มากกว่า $Y$) 7:51 AM 9/10/2023

ทั้งปัญหานี้จึงใช้เวลา $\mathcal{O}(L \log{} L + L + Q \log{} L) = \mathcal{O}((Q+L) \log{} L)$