E-Crying 与初中数学_牛客挑战赛72

时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Crying 正在学习初中数学。

今天他学到了如何化简 $\sqrt n$ ，其中 $n$ 是一个正整数。他想到，如果给出一个很大的 $N$ ，要求你化简所有 $\sqrt n$ ，其中 $n = 1, 2, \dots, N$ ，这个问题就会变得稍微有趣一点。

为了显得善良一些，若 $\sqrt n$ 化简为 $a_n \sqrt{b_n}$ ，则你只需要求出

\sum_{n=1}^N (a_n + b_n) \bmod 2^{64}

其中称 $\sqrt n$ 化简为 $a_n \sqrt b_n$ 当且仅当 $(a_n, b_n)$ 在所有满足 $\sqrt n = a \sqrt b$ 的正整数对 $(a, b)$ 中是 $a$ 最大的那个。

第一行，一个正整数 $N$ 。

对于所有数据， $1 \le N \le 1.5 \times 10^{16}$ 。

一行，一个非负整数，表示答案。

示例1

复制

复制

有

；
；
；
；
。

故答案为 。

示例2

复制

10000000

复制

32898926882292