Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Lưu ý: Trên web đọc dữ liệu từ bàn phím (stdin) và in ra màn hình (stdout).

Nguồn: Câu 2 – Kỳ thi lập đội tuyển học sinh giỏi dự thi cấp quốc gia THPT năm học 2022-2023, Sở GD&ĐT Tiền Giang (ngày thi thứ nhất 04/10/2022) · Codeforces 1541B – Pleasant Pairs.

Cho dãy số nguyên ~a_1, a_2, \ldots, a_n~ chứa ~n~ số nguyên phân biệt. Một cặp số ~(i, j)~ với ~(i < j)~ được gọi là kì diệu khi ~a_i \cdot a_j = i + j~.

Hãy đếm số cặp số kì diệu trong dãy ~a~.

Dữ liệu vào

• Dòng 1: chứa số nguyên dương ~t~ ~(1 \le t \le 10^4)~ là số bộ dữ liệu trong test này.
• Dòng đầu tiên trong mỗi bộ dữ liệu gồm số nguyên ~n~ ~(1 \le n \le 10^5)~ là số lượng số hạng của dãy ~a~.
• Dòng tiếp theo trong mỗi bộ dữ liệu gồm ~n~ số nguyên phân biệt ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le 2n)~.

Kết quả

• Với mỗi bộ dữ liệu, ghi ra một số nguyên duy nhất là số cặp số kì diệu trong dãy ~a~, mỗi kết quả trên một dòng.

Giới hạn

• Gọi ~S~ là tổng các số nguyên ~n~ trong mỗi test.
• Subtask 1 (50%): ~S \le 10^3~.
• Subtask 2 (50%): ~S \le 2 \cdot 10^5~.
• Giới hạn thời gian: 1 giây.

Sample Input 1

3
2
3 1
3
6 1 5
5
3 1 5 9 2

Sample Output 1

1
1
3

Giải thích

• Trong bộ dữ liệu đầu tiên, cặp số kì diệu duy nhất là ~(1, 2)~ vì ~a_1 \cdot a_2 = 1 + 2 = 3~.
• Trong bộ dữ liệu thứ hai, cặp số kì diệu thoả mãn là ~(2, 3)~.
• Trong bộ dữ liệu thứ ba, có 3 cặp số kì diệu ~(1, 2)~, ~(1, 5)~ và ~(2, 3)~.