問題一覧 > 通常問題

No.1514 Squared Matching

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 123
作問者 : だれだれ / テスター : evimaevima nok0nok0
14 ProblemId : 6365 / 出題時の順位表 / 自分の提出
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。