No.1514 Squared Matching
レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 123
作問者 :
だれ
/ テスター :
evima
nok0
タグ : / 解いたユーザー数 123
作問者 :
だれ
/ テスター :
evima
nok0
問題文最終更新日: 2021-05-02 17:05:28
問題文
$1$ 以上 $N$ 以下の整数の順序対 $(a, b)$ であって、積 $ab$ が平方数であるようなものの個数を求めてください。
注記
実行時間制限に注意してください。（C++ であれば、実行制限時間を $1/4$ にしても解けることを確認しています。）
入力
$N$
- $1 \leq N \leq 5 \times 10^7$
- $N$ は整数
出力
答えを出力し、末尾で改行してください。
サンプル
サンプル1
入力
4
出力
6
$(a, b) = (1, 1), (1, 4), (2, 2), (3, 3), (4, 1), (4, 4)$ の $6$ 通りです。
サンプル2
入力
50000000
出力
545761220
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。