题目

很久很久以前，有一只神犇叫yzy;

很久很久之后，有一只蒟蒻叫lty;

输入格式

请你读入一个整数N;1<=N<=1E9,A、B模1E9+7;

输出格式

请你输出一个整数A=\sum_{i=1}^N{\mu (i^2)};

请你输出一个整数B=\sum_{i=1}^N{\varphi (i^2)};

输入样例

1

输出样例

1

1

题解

首先很明显= =

\[ans1 = 1\]

然后重点是\(ans2\)

我们会发现这样一个性质：

\[\varphi(i^2) = i*\varphi(i)\]

证明：

\(i^2\)与\(i\)拥有相同的质因子，所以与\(i\)互质的同样与\(i^2\)互质，与\(i\)不互质的同样与\(i^2\)不互质

由于\(gcd(i,j) = gcd(i + i,j)\)，且\(i^2 = i * i\)，所以\(\varphi(i^2) = i * \varphi(i)\)

【ps:突然发现我傻逼了，直接上\(\varphi\)的计算公式就得证了QAQ】

然后就可以筛了：

我们令

\[f(i) = i * \varphi(i)\]

拿出杜教筛的套式：

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

我们企图找出这样一个好算的\(g(i)\)

考虑卷积：

\[(f * g)(n) = \sum\limits_{d|n} g(\frac{n}{d}) * d * \varphi(d)\]

我们想把\(\varphi(d)\)外的变为常数，这样可以提出来，成为\(\varphi * 1 = Id\)

很容易发现，如果\(g = Id\)，那么就刚好可以做到：

\[(Id * f)(n) = \sum\limits_{d|n} \frac{n}{d} * d * \varphi(d) = n * \sum\limits_{d|n} \varphi(d) = n^2\]

再由：

\[\sum\limits_{i=1}^{n} i^2 = \frac{n * (n + 1) * (2 * n + 1)}{6}\]

那么杜教筛的式子就化成了：

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

就可以做了

#include
    
     #include
     
      #include
      
       #include