An interesting counting problem related to square product 2
Xem PDF
Điểm:
300 (p)
Thời gian:
1.0s
Bộ nhớ:
1G
Input:
bàn phím
Output:
màn hình
Given \(n (1 \leq n \leq 10^6)\), count the number of pairs \((a, b)\) that satisfies:
- \(1 \leq a < b \leq n\).
- \(a \times b\) is a perfect square.
Since the result can be large, output it under modulo \(10^9 + 7\).
Example
Test 1
Input
1Output
0Note
There are no satisfied integer pair \((a, b)\) that \(1 \leq a < b \leq 1\).
Test 2
Input
10Output
4Note
There are \(4\) satisfied pairs: {\(1, 4\)}, {\(1, 9\)}, {\(2, 8\)}, {\(4, 9\)}.
Test 3
Input
25Output
16Note
There are \(16\) satisfied pairs: {\(1, 4\)}, {\(1, 9\)}, {\(1, 16\)}, {\(1, 25\)}, {\(2, 8\)}, {\(2, 18\)}, {\(3, 12\)}, {\(4, 9\)}, {\(4, 16\)}, {\(4, 25\)}, {\(5, 20\)}, {\(6, 24\)}, {\(8, 18\)}, {\(9, 16\)}, {\(9, 25\)}, {\(16, 25\)}.
Bình luận
Dịch ra là:Một bài toán đếm thú vị liên quan đến tích bình phương 2
Cho n (1 ≤ n ≤ 10^6), đếm số cặp (a, b) thỏa mãn:
1 ≤ a < b ≤ n.
a × b là một số chính phương.
Do kết quả có thể lớn, hãy xuất kết quả dưới dạng modulo 10^9 + 7.
Use the google translate
pleaseee give me vietnameseee:)
:((