LQDOJ Contest #9 - Bài 1 - Số Đặc Biệt

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
shiba
Dạng bài
Điểm: 1800 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một số nguyên dương \(N\) là một số đặc biệt khi tổng các ước số của nó (trừ chính nó) lớn hơn \(M\) với \(M\) là một số nguyên dương được cho trước. Ví dụ với \(M = 5\) thì \(N = 6\) là số đặc biệt vì \(1 + 2 + 3 = 6 > 5\). Nhưng với \(M = 6\) hay \(M = 10\) thì \(N = 6\) không phải số đặc biệt.

Yêu cầu: Cho \(Q\) truy vấn, mỗi truy vấn có ba số nguyên dương lần lượt là \(L,R,X\). Bạn hãy đếm số đặc biệt có trong đoạn \([L;R]\) tính theo \(X\). Nói cách khác, bạn hãy đếm số thỏa mãn rằng tổng các ước số của nó (trừ chính nó) lớn hơn \(X\) có trong đoạn \([L;R]\).

Input

  • Dòng đầu tiên chứa số nguyên dương \(Q\) \((1 \le Q \le 10^5)\).
  • \(Q\) dòng tiếp theo mỗi dòng chứa ba số nguyên dương lần lượt là \(L,R,X\) \((1 \le L \le R \le 10^5, 1 \le X \le 10^5)\).

Output

  • In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

  • Subtask \(1\) (\(10\%\) số điểm): Có \(Q,R \le 10^3\).

  • Subtask \(2\) (\(20\%\) số điểm): Có \(R \le 10^4\) và \(X = 10\).

  • Subtask \(3\) (\(30\%\) số điểm): Có \(X \le 10\).

  • Subtask \(4\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input 
2
1 10 5
15 20 8
Output 
3
4
Note
  • Với truy vấn đầu tiên thì \(3\) số thỏa mãn là \((6,8,10)\).
  • Với truy vấn thứ hai thì \(4\) số thỏa mãn là \((15,16,18,20)\).

Bình luận