#P2818. Gcd

    ID: 1924 传统题 1000ms 512MiB 尝试: 11040 已通过: 2536 难度: 5 上传者: 标签>CF1800普及+/提高-欧拉函数线性筛一维前缀和交换求和顺序素数计数湖北省队互测

Gcd

题目描述

令 PP 表示所有素数组成的集合。

给定正整数 NN,求

∑i=1N∑j=1N[gcd⁡(i,j)∈P]\sum_{i=1}^N\sum_{j=1}^N [\gcd(i,j)\in P]

其中 [][] 表示艾佛森括号,当表达式 AA 为真时,[A][A] 为 11,反之为 00。

输入格式

一个正整数 NN。

输出格式

输出对应答案。

4
4

提示

对于样例 (2,2),(2,4),(3,3),(4,2)(2,2),(2,4),(3,3),(4,2)。

1≤N≤1071\le N\le 10^7。

题目来源

湖北省队互测