D - Together Square
Editorial
/


Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
整数 N が与えられます。以下の条件を満たす N 以下の正整数の組 (i,j) の個数を求めてください。
- i \times j は平方数である。
制約
- 1 \le N \le 2 \times 10^5
- N は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
4
出力例 1
6
(1,1),(1,4),(2,2),(3,3),(4,1),(4,4) の 6 個が条件を満たします。
(2,3) は 2 \times 3 =6 が平方数でないため条件を満たしません。
入力例 2
254
出力例 2
896
Score : 400 points
Problem Statement
You are given an integer N. Find the number of pairs (i,j) of positive integers at most N that satisfy the following condition:
- i \times j is a square number.
Constraints
- 1 \le N \le 2 \times 10^5
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
4
Sample Output 1
6
The six pairs (1,1),(1,4),(2,2),(3,3),(4,1),(4,4) satisfy the condition.
On the other hand, (2,3) does not, since 2 \times 3 =6 is not a square number.
Sample Input 2
254
Sample Output 2
896