#P2226. [Spoj 5971] LCMSum

    ID: 1251 传统题 1000ms 259MiB 尝试: 2389 已通过: 738 难度: 5 上传者: 标签>CF1800普及+/提高-最小公倍数欧拉函数线性筛倍数枚举对称性分析

[Spoj 5971] LCMSum

题目描述

TT 次询问,每次询问给定 nn,求

∑i=1nlcm⁡(i,n)\sum_{i=1}^n\operatorname{lcm}(i,n)

输入格式

第一行一个整数 TT,接下来 TT 行,每行 11 个整数 nn

输出格式

对每组询问,输出答案。

3
1
2
5
1
4
55

提示

1≤T≤3×1051\le T\le 3\times 10^5,1≤n≤1061\le n\le 10^6

题目来源

没有写明来源