#P4805. 欧拉函数求和

    ID: 3922 传统题 5000ms 256MiB 尝试: 1142 已通过: 429 难度: 7 上传者: 标签>CF2200提高+/省选-欧拉函数杜教筛整除分块线性筛记忆化搜索交换求和顺序一维前缀和ByFancyCoder

欧拉函数求和

题目描述

给出一个数字 nn,求 ∑i=1nφ(i)\sum\limits_{i=1}^n\varphi(i)。

输入格式

正整数 nn。

输出格式

输出答案。

样例输入

10

样例输出

32

数据范围与约定

对于 100%100\% 的数据,1≤n≤2×1091\le n\le 2\times 10^9。

题目来源

By FancyCoder