#P4804. 欧拉心算

    ID: 3921 传统题 3000ms 256MiB 尝试: 1049 已通过: 398 难度: 7 上传者: 标签>CF2200提高莫比乌斯反演狄利克雷卷积交换求和顺序线性筛筛法计算积性函数一维前缀和整除分块ByFancyCoder

欧拉心算

题目描述

给定 nn,求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^n\varphi(\gcd(i,j))$。

输入格式

第一行为一个正整数 TT,表示数据组数。

接下来 TT 行为询问,每行包含一个正整数 nn。

输出格式

按读入顺序输出答案。

1
10
136

数据范围与约定

对于 100%100\% 的数据,T≤5×103T\le 5\times 10^3,n≤107n\le 10^7。

题目来源

By FancyCoder