#P13764. [2019年备战北大冬令营]王队的sum

    ID: 12966 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-Min_25 筛整除分块欧拉函数线性筛同余的加减乘运算

[2019年备战北大冬令营]王队的sum

题目描述

给定 nn,请你求出

$$\sum_{i=1}^{n}\sum_{j=1}^{i}\sum_{k=1}^{i}[(i,j),(i,k)]$$

答案对 2322^{32} 取模。

说明:按竞赛中常见记号,(a,b)(a,b) 往往表示 gcd⁡(a,b)\gcd(a,b),[a,b][a,b] 往往表示 lcm(a,b)\mathrm{lcm}(a,b)

输入格式

一行一个数 n(n≤9233333333)n(n\le 9233333333) 描述询问。

输出格式

一行一个数表示答案。

Samples

23
18690