Description

Input

一共T+1行

第1行为数据组数T(T<=10)

第2~T+1行每行一个非负整数N，代表一组询问

Output

一共T行，每行两个用空格分隔的数ans1,ans2

Sample Input

612813302333

Sample Output

1 12 022 -258 -3278 -31655470 2

solution

杜教筛模板题无敌卡常题．

先搬出套路式子：

\[ S(n)=\sum_{i=1}^{n}(f*g)(i)-\sum_{i=2}^{n}g(i)S(\lfloor\frac{n}{i}\rfloor) \]

对于\(\mu(n)\)，拿一个\(I(n)=1\)和他卷起来，可以得到：

\[ S(n)=1-\sum_{i=2}^{n}S(\lfloor\frac{n}{i}\rfloor) \]

对于\(\varphi(n)\)，同样拿一个\(I(n)\)卷起来，得到：

\[ S(n)=\frac{n*(n+1)}{2}-\sum_{i=2}^{n}S(\lfloor\frac{n}{i}\rfloor) \]

然后飞速的敲完代码，提交，\(TLE\)......

可能是我太弱了，所有的卡常技巧都用上了，然而并没有什么用....

然后突然发现一个这样的事情：

对于\(\varphi(n)\)，其实可以写成这个样子：

\[ \varphi(n)=\sum_{i=1}^{n}\epsilon(\gcd(i,n)) \]

其中\(\epsilon(n)=[n=1]\)．

然后苦思冥想无果后闲着无聊对前缀和反演下：

\[ \begin{align} S(n)&=\sum_{i=1}^{n}\sum_{d=1}^i\epsilon(\gcd(d,i))\\ &=\sum_{i=1}^{n}\sum_{d=1}^i\sum_{d_1|i\&d_1|d}\mu(d_1)\\ &=\sum_{i=1}^{n}\sum_{d_1|i}\sum_{d=1}^{\frac{i}{d_1}}\mu(d_1)\\ &=\sum_{i=1}^n\sum_{d_1|i}\mu(d_1)\frac{i}{d_1}\\ &=\sum_{d_1=1}^n\sum_{i=1}^{\frac{n}{d_1}}\mu(d_1)*i\\ &=\sum_{d_1=1}^n\mu(d_1)*\frac{\lfloor\frac{n}{d_1}\rfloor(\lfloor\frac{n}{d_1}\rfloor+1)}{2} \end{align} \]

然后惊奇的发现，这里面用到的\(\mu(n)\)的前缀和正好是第二问要求的，然后这么一来直接快了一倍不止，成功的只跑了\(6sAC\)。

#include
    
     using namespace std;#define ll long long void read(int &x) {    x=0;int f=1;char ch=getchar();    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;}void print(int x) {    if(x<0) x=-x,putchar('-');    if(!x) return ;print(x/10),putchar(x%10+48);}void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}const int maxn = 3e6+1;int pri[maxn],vis[maxn],n,tot,inv2,inv6,mu[maxn];void sieve() {    mu[1]=1;    for(int i=2;i
     
       Mu;/*ll sum_phi(int n) {    if(n