An interesting counting problem related to square product 2

Xem PDF
Tác giả:
SPyofgame , SPectiar2k
Dạng bài
Đ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 
1
Output 
0
Note

There are no satisfied integer pair \((a, b)\) that \(1 \leq a < b \leq 1\).

Test 2

Input 
10
Output 
4
Note

There are \(4\) satisfied pairs: {\(1, 4\)}, {\(1, 9\)}, {\(2, 8\)}, {\(4, 9\)}.

Test 3

Input 
25
Output 
16
Note

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