前置相关

• 类型积性函数（注：以下皆为完全积性函数，即无需满足 \(x \perp y\) 即有 \(f(x)f(y) = f(xy)\)

  \(\epsilon (n) = [n = 1]\)

  \(id (n) = n\)

• 狄利克雷卷积与欧拉函数

  此处若以 $id $ 作单位元，则 \(1\) 为 \(\phi\) 的逆，即 \(\phi * 1 = id\)

  证明：由 \(\sum\limits_{d | n} \phi (d) = n\) ，再带回原式可证

• 莫比乌斯函数与欧拉函数的转化

  \[\begin{aligned} \phi * 1 &= id \\ \phi * 1 * \mu &= id * \mu \\ \phi * \epsilon &= id * \mu \\ \phi &= \sum\limits_{d | n} \mu(d) \frac{n}{d} \\ \frac{\phi}{n} &= \sum\limits_{d | n} \frac{\mu(d)}{d} \end{aligned}\]

杜教筛

• 杜教筛用于求解积性函数前缀和一类问题

• 下面求解积性函数 \(f\) 的前缀和

• 设积性函数 \(f, g, h\) ，且 \(h = f * g\) ，则有

\[\begin{aligned} \sum\limits_{i = 1}^n h(n) &= \sum\limits_{i = 1}^n \sum\limits_{d | n} g(d)f(\frac{n}{d}) \\ &= \sum\limits_{d = 1}^n g(d) \sum\limits_{i = 1}^{\left\lfloor\frac{n}{d}\right\rfloor} f(i) \end{aligned}\]

• 令 \(S(n) = \sum\limits_{i = 1}^n f(i)\)
• 将 \(d = 1\) 时的提出，再移项，得

\[S(n) = \sum\limits_{i = 1}^n h(i) - \sum\limits_{d = 2}^n g(d)S(\left\lfloor\frac{n}{d}\right\rfloor)\]

• 那么预处理 \(h, g\) 的前缀和（一般预处理 \(n^{\frac{2}{3}}\) 个？），再递归整除分块即可处理，不过一般 \(h, g\) 需要自己配

例

• 求\(\sum\limits_{i = 1}^n \mu(i), \sum\limits_{i = 1}^n \phi(i)\)

由 \(\mu * 1 = \epsilon\) ，可令 \(g = 1, h = \epsilon\) ，那么得到

\[S(n) = 1 - \sum\limits_{d = 2}^n S(\left\lfloor\frac{n}{d}\right\rfloor)\]

求 \(\sum \phi\) 同理

• 求\(\sum\limits_{i = 1}^n i \phi(i)\) （需要用配的）

\[h(n) = \sum\limits_{d | n} d \phi(d) g(\frac{n}{d})\]

希望将 \(d\) 消去，故配 \(g = id\) ，得 \(h(n) = n^2\)

\[S(n) = \sum\limits_{i = 1}^n i^2 - \sum\limits_{d = 2}^n d S(\left\lfloor\frac{n}{d}\right\rfloor)\]

即可解

代码（求解\(\sum \mu, \sum \phi\) ）

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long LL;const int MAXN = 5e06 + 10;int prime[MAXN / 10];int vis[MAXN]= {0};int pcnt = 0;int mu[MAXN]= {0};LL phi[MAXN]= {0};int sumu[MAXN]= {0};LL sumphi[MAXN]= {0};const int MAX = 4e06 + 5e05;void linear_sieve () {    mu[1] = phi[1] = 1;    for (int i = 2; i <= MAX; i ++) {        if (! vis[i]) {            prime[++ pcnt] = i;            mu[i] = - 1, phi[i] = i - 1;        }        for (int j = 1; j <= pcnt && i * prime[j] <= MAX; j ++) {            vis[i * prime[j]] = 1;            if (! (i % prime[j])) {                phi[i * prime[j]] = phi[i] * prime[j];                break;            }            mu[i * prime[j]] = - mu[i];            phi[i * prime[j]] = phi[i] * (prime[j] - 1);        }    }    for (int i = 1; i <= MAX; i ++) {        sumu[i] = sumu[i - 1] + mu[i];        sumphi[i] = sumphi[i - 1] + phi[i];    }}int T;int N;tr1::unordered_map
        
          mapmu;tr1::unordered_map
         
           maphi;int mu_sieve (int n) { if (n <= MAX) return sumu[n]; if (mapmu[n]) return mapmu[n]; int total = 1; for (int l = 2, r; l <= n; l = r + 1) { r = n / (n / l); total -= (r - l + 1) * mu_sieve (n / l); } return mapmu[n] = total;}LL phi_sieve (int n) { if (n <= MAX) return sumphi[n]; if (maphi[n]) return maphi[n]; LL total = n * 1ll * (n + 1) / 2ll; for (int l = 2, r; l <= n; l = r + 1) { r = n / (n / l); total -= 1ll * (r - l + 1) * phi_sieve (n / l); } return (maphi[n] = total);}int main () { linear_sieve (); scanf ("%d", & T); for (int Case = 1; Case <= T; Case ++) { scanf ("%d", & N); LL ans1 = phi_sieve (N); int ans2 = mu_sieve (N); printf ("%lld %d\n", ans1, ans2); } return 0;}/*612813302333*//*518800717261727918194180845553730126*/