#P3944. Sum

    ID: 3150 传统题 1000ms 128MiB 尝试: 10398 已通过: 1178 难度: 7 上传者: 标签>CF2300提高+/省选-杜教筛狄利克雷卷积整除分块线性筛筛法计算积性函数一维前缀和记忆化搜索哈希表交换求和顺序

Sum

题目描述

给定一个非负整数 NN,求 ans1=∑i=1Nφ(i)\text{ans1}=\sum\limits_{i=1}^N\varphi(i),ans2=∑i=1Nμ(i)\text{ans2}=\sum\limits_{i=1}^N\mu(i),多组询问。

输入格式

输入一共 T+1T+1 行。

第一行为数据组数 TT。

接下来 TT 行,每行一个非负整数 NN,代表一组询问。

输出格式

一共 TT 行,每行两个用空格分隔的数 ans1,ans2\text{ans1},\text{ans2}。

6
1
2
8
13
30
2333
1 1
2 0
22 -2
58 -3
278 -3
1655470 2

数据范围与提示

对于 100%100\% 的数据,0≤N≤231−10\le N\le 2^{31}-1,1≤T≤101\le T\le 10。