2021-03-12 22:31 已编辑东北林业大学 Python

关注

欧拉函数+卷积+莫比乌斯函数+莫比乌斯反演+整除分块+杜教筛

欧拉函数

定义：对于一个正整数n，小于n且和n互质的正整数（包括1）的个数，记作φ(n) 。

欧拉函数通式： $φ(n)=n\prod_{i=1}^k(1-\frac{1}{p_i})$
其中 $p_1, p_2……p_k$ 为 $n$ 的所有质因数， $n∈N^+$ 。特别的 $φ(1)=1$ 。

所以根据通式可以直接求出一个数的欧拉值

ll euler(ll n){
    ll ans = n;
    for(int i = 2; i * i <= n; i ++){
        if(!(n % i)){
            ans = ans / i * (i - 1);
            while(!(n % i)) n /= i;
        }
    }
    if(n > 1) ans = ans / n * (n - 1);
    return ans;
}

性质：

欧拉函数为积性函数。

积性函数：对于函数 $f$ ，当 $gcd(a,b)=1$ , $f(ab)=f(a)f(b)$
完全积性函数：特别地，对于任意的 $a,b$ ，即 $gcd(a,b)≠1$ ，也有 $f(ab)=f(a)f(b)$
所以 $φ(ab)= φ(a)φ(b)$
当且仅当 $gcd(a,b)=1$ ，即 $a,b$ 互质。
特别地，假如 $a,b$ 不互质，则 $φ(ab)= \frac{φ(a)φ(b)gcd(a,b)}{φ(gcd(a,b))}$
这个便为通式。
以上证明均略。

衍生出的性质： $φ(2×b)= φ(b)$
当且仅当 $b$ 为奇数时。

对于一个质数 $p$ ， $φ(p)=p−1$
无需证明，根据定义即可推出。
所以，即可在线性筛的时候，打出欧拉函数的表

  namespace prime_sieve_phi{
      const int N = 1e7 + 5;
      int  cnt, sum, ans, prime[N], pre[N], phi[N];
      bool flag[N];
      void init()
      {
          memset(flag, 1, sizeof(flag));
          flag[1] = 0;
          cnt = 0;
          phi[1] = 1;
          for(int i = 2; i <= N; i++)
          {
              if(flag[i])
              {
                  prime[++cnt] = i;
                  pre[i] = cnt;
                  phi[i] = i - 1;
              }
              for(int j = 1; j <= cnt && 1ll * prime[j] * i <= N; j++)
              {
                  flag[prime[j] * i] = 0;
                  if(i % prime[j] == 0) {
                      phi[i * prime[j]] = phi[i] * prime[j];
                      break;
                  }
                  phi[i * prime[j]] = phi[i] * (prime[j] - 1);
              }
          }
      }
  }
  using namespace prime_sieve_phi;

对于一个质数 $p$ ， $φ(p^k )= p^k −p^{k−1} = p^{k−1} ×(p−1)= p^{k−1} ×φ(p)$
证明：
- 首先， $φ(p^k )= p^k - (1 …… p^k中与p不互素的数的个数)$ ， $1……p$ 与 $p$ 不互质的数有 $p^0$ 个(即 $p$ )， $1……p^2$ 与 $p$ 不互质的数有 $p^1$ 个，……， $1……p^k$ 与 $p$ 不互质的数有 $p^{k-1}$ 个。
  则 $φ(p^k )= p^k −p^{k−1}$
- 其次，提取公因式，得 $φ(p^k )=p^{k−1} ×(p−1)$
- 最后，根据性质二，得 $φ(p^k )=p^{k−1} ×φ(p )$
$n=\sum_{d|n} φ(d)$
即 $n$ 的因数（包括 $1$ 和它自己）的欧拉函数之和等于 $n$ 。
也就是 $φ * I = id$ （后面有）

经典的应用为 $\sum_{d|gcd(i,j)} φ(d) = gcd(i,j)$
当 $n>2$ 时， $φ(n)$ 是偶数。

证明：
首先前提：若 $gcd(a,b) = d$ 且 $a>b$ ，则 $gcd(a,a-b) = d$
若 $a$ 与 $b$ 互质，则 $gcd(a,b) = 1$ ， $gcd(a,a-b) = 1$ $(a>b)$
我们假设 $b=a-b$ ，则 $a=2×b$
则当 $a>2$ 时， $gcd(a,b) ≠ 1$ ，与前提矛盾，故假设不成立。
所以 $a≠2×b$
说明了 $a>2$ 时， $a$ 与 $b$ 互质， $a$ 与 $a-b$ 互质，也就是说：** $a>2$ 时，与 $a$ 互质的数是成对出现的**，所以 $φ(n)$ 是偶数。
对于一个正整数 $n$ ，小于 $n$ 且和 $n$ 互质的正整数（包括 $1$ ）的和，记作 $sum\_φ(n)$ ~~（乱叫的）~~ 。

$sum\_φ(n)= \begin{cases} 1 & & n=1 \\ \frac{φ(n) × n} {2} & &n>2 \end{cases}$

证明：
* $n=1$，略
* $n>2$，由于此时，**与$n$互质的数是成对出现**，且每一对里除了$n$以外的数为$m$与$n-m$，则它们的和便为$n$。由于会重复计算，故除以$2$，与$n$互质的数的个数为$φ(n)$，得证。

狄利克雷卷积

狄利克雷卷积是函数之间的运算 $(f * g)(n) = \sum_{d|n}f(d)g(\frac{n}{d})$
$(f * g)(n) = \sum_{d|n}f(\frac{n}{d})g(d)$

性质：

假如做狄利克雷卷积的两个函数 $f$ 和 $g$ 都是积性函数，那么 $f ∗ g$ 也是积性函数。
满足交换律，结合律，分配律。

常见的积性函数及狄利克雷卷积

幂函数 $idk(n) = n^k$
单位函数 $id(n) = n$ （幂函数 $k = 1$ 的情况）
不变函数 $I(n) = 1$ （幂函数 $k = 0$ 的情况）
欧拉函数 $φ(n)$ ， $φ * I = id$
莫比乌斯函数 $μ(n)$ ， $μ * id = φ$ ， $μ * I = ε$ （左式和上式可推出）
狄利克雷卷积单位元 $ε(n) = [n == 1]$
因子个数函数 $d(n)$ ， $I * I = d$
因子和函数 $σ(n)$ ， $I * id= σ$
因子函数 $σk(n)$ ， $I * idk= σk$
其中 $ε,I,id$ 为完全积性函数

莫比乌斯函数

定义：

$μ(n)= \begin{cases} 1 & &n=1 \\ (-1)^m & &n= p_1 × p_2 ……×p_k \ (p_i为互异素数)\\ 0 & & otherwise \end{cases}$

性质：

莫比乌斯函数为积性函数
故可以线性筛出来。

  namespace prime_sieve_mu{
      const int N = 1e7 + 5;
      int  cnt, sum, ans, prime[N], pre[N], mu[N];
      bool flag[N];
      void init()
      {
          memset(flag, 1, sizeof(flag));
          flag[1] = 0;
          mu[1] = 1;
          cnt = 0;
          for(int i = 2; i <= N; i++)
          {
              if(flag[i])
              {
                  prime[++cnt] = i;
                  pre[i] = cnt;
                  mu[i] = -1;
              }
              for(int j = 1; j <= cnt && 1ll * prime[j] * i <= N; j++)
              {
                  flag[prime[j] * i] = 0;
                  if(i % prime[j] == 0) {
                      mu[prime[j] * i] = 0;
                      break;
                  }
                  else{
                      mu[prime[j] * i] = -mu[i]; 
                      //互异因子
                  }
              }
          }
      }
  }
  using namespace prime_sieve_mu;

有平方因子的数的莫比乌斯函数值为 $0$
$\sum_{d|n} μ(d) = [n==1]$
如果狄利克雷卷积看懂了，这个式子其实就是 $μ*I=ε$
这个可以说是最常用的性质

经典的应用为 $\sum_{d|gcd(i,j)} μ(d) = [gcd(i,j)==1]$
证明：由定义得 $\sum_{d|n} μ(d)= \begin{cases} 1 & &n=1 \\ 0 & & n>1 \end{cases}$
$\sum_{d|n} μ(d) × \frac{n}{d} = φ(n)$

这个式子其实就是 $μ * id = φ$
这个便为莫比乌斯函数和欧拉函数的关系。
这个式子的另外一个变式为 $\sum_{d|n} \frac{μ(d)}{d} = \frac{φ(n)}{n}$

莫比乌斯反演

两种形式：

约数形式： $g(n) = \sum_{d|n}f(d) \to f(n) = \sum_{d|n}μ(d)g(\frac{n}{d})$
简单证明： $g = f * I$
$μ * g = μ * f * I = f * ε = f$
倍数形式： $g(n) = \sum_{n|d}f(d) \to f(n) = \sum_{n|d}μ(\frac{d}{n})g(d)$

例题：

P3455 [POI2007]ZAP-Queries

传送门：https://www.luogu.com.cn/problem/P3455
求 $\sum_{i=1} ^ n\sum_{j=1} ^ m[gcd(i,j) ==d]$
每一个推导，我都尽力把坑都讲一下，帮助理解。 $\begin{aligned} \sum_{i=1} ^ n\sum_{j=1} ^ m[gcd(i,j) ==d] &= \sum_{i=1} ^ {\lfloor{\frac{n}{d}}\rfloor}\sum_{j=1} ^ {\lfloor{\frac{m}{d}}\rfloor}[gcd(i,j) ==1]\\ &= \sum_{i=1} ^ {\lfloor{\frac{n}{d}}\rfloor}\sum_{j=1} ^ {\lfloor{\frac{m}{d}}\rfloor} \sum_{k|gcd(i,j)} μ(k) \\ &= \sum_{i=1} ^ {\lfloor{\frac{n}{d}}\rfloor}\sum_{j=1} ^ {\lfloor{\frac{m}{d}}\rfloor} \sum_{k|i,k|j} μ(k) \\& 令 \ tmp = min(\lfloor{\frac{n}{d}}\rfloor,\lfloor{\frac{m}{d}}\rfloor)\\ & ps:更改枚举顺序，改为枚举k，然后i和j的上限改变 \\ &= \sum_{k=1} ^ {tmp}μ(k)\sum_{k|i} ^ {\lfloor{\frac{n}{d}}\rfloor}\sum_{k|j} ^ {\lfloor{\frac{m}{d}}\rfloor} \\ &= \sum_{k=1} ^ {tmp}μ(k)\sum_{i=1} ^ {\lfloor{\frac{n}{kd}}\rfloor}\sum_{j=1} ^ {\lfloor{\frac{m}{kd}}\rfloor} \\ &= \sum_{k=1} ^ {tmp}μ(k) \lfloor\frac{n}{kd} \rfloor\lfloor\frac{m}{kd} \rfloor \end{aligned}$
帮助理解：

变化前： $\sum_{d=1}^n\sum_{d|i}^ {n}$
变化后： $\sum_{d=1}^n\sum_{i=1} ^ {\lfloor{\frac{n}{d}}\rfloor}$

这两个 $i$ 的含义是不一样的！！！

变化前的 $i$ ： $i$ 从 $1 \to n$ 的因子为 $d$ ，比如 $n = 6$
- $d =1$ , $i = 1,2,3,4,5,6$
- $d =2$ , $i = 2,4,6$
- $d =3$ , $i = 3,6$
- $d =4$ , $i = 4$
- $d =5$ , $i = 5$
- $d =6$ , $i = 6$
变化后的 $i$ ：式子其实是这样的： $\sum_{d=1}^n\sum_{d×i=1} ^ {n}$ ，比如 $n = 6$
- $d =1$ , $i = 1,2,3,4,5,6$
- $d =2$ , $i = 1,2,3$
- $d =3$ , $i = 1,2$
- $d =4$ , $i = 1$
- $d =5$ , $i = 1$
- $d =6$ , $i = 1$
  
  $d ×i$ 就是从 $1 \to n$ 中是 $d$ 的倍数的数。

所以说两个 $i$ 的含义不同，千万不要混淆，我这么写只是为了后面写的时候方便推导。

公式推出来了，那后面那一坨怎么求呢？

整除分块

对于这种式子： $\sum_{i=1} ^ {n} 1×\lfloor \frac{n}{i} \rfloor$
很明显，处理起来可以做到 $O(n)$ ，但通过打表可以发现有许多 $\lfloor \frac{n}{i} \rfloor$ 的值是一样的，并且成块状分布，那么就可以求出这一个块的 $l$ 和 $r$ 。这样一个块一个块地求，就会将复杂度降低到 $O(\sqrt{n})$

比如上面的式子的代码为

for(int l = 1, r; l <= n; l = r + 1)
{
    r = n / (n / l);
    ans += (r - l + 1) * (n / l);
}

所以例题代码为

#include<bits/stdc++.h>
using namespace std;
#define ll                          long long
#define ull                         unsigned long long
#define ld                          long double
#define db                          double
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define mset(s, _)                  memset(s, _, sizeof(s))
#define lowbit(x)                   ((x) &-(x))
#define IOS                         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl                        "\n"
typedef pair<int, int>               pii;
typedef pair<ll, ll>                 pll;
namespace prime_sieve_mu{
    const int N = 5e4 + 5;
    int  cnt, ans, prime[N], mu[N], sum[N], pre[N];
    bool flag[N];
    inline void init(){
        memset(flag, 1, sizeof(flag));
        flag[1] = 0;
        mu[1] = 1;
        cnt = 0;
        for(int i = 2; i <= N; i++)
        {
            if(flag[i]){
                prime[++cnt] = i;
                pre[i] = cnt;
                mu[i] = -1;
            }
            for(int j = 1; j <= cnt && 1ll * prime[j] * i <= N; j++){
                flag[prime[j] * i] = 0;
                if(i % prime[j] == 0) {
                    mu[prime[j] * i] = 0;
                    break;
                }
                else{
                    mu[prime[j] * i] = -mu[i];
                }
            }
        }
        for(int i = 1; i <= N; i++) {
            sum[i] = sum[i - 1] + mu[i];
        }
    }
}
using namespace prime_sieve_mu;
int a, b, d, n;
int main()
{
    scanf("%d", &n);
    init();
    while(n --){
        ll ans = 0;
        scanf("%d%d%d", &a, &b, &d);
        a /= d; b /= d; //这里要先整除d,因为上界不是a,而是a/d
        int tmp = min(a, b);
        for(int l = 1, r; l <= tmp; l = r + 1){
            r = min(a / (a / l), b / (b / l));
            ans += (1ll) * (sum[r] - sum[l - 1]) * (a / l) * (b / l);
            // (1ll) 是要加的
        }
        printf("%lld\n", ans);
    }
    return 0;
}

P2522 [HAOI2011]Problem b

传送门：https://www.luogu.com.cn/problem/P2522

和上一个题一样，运用一下容斥即可。

#include<bits/stdc++.h>
using namespace std;
#define ll                          long long
#define ull                         unsigned long long
#define ld                          long double
#define db                          double
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define mset(s, _)                  memset(s, _, sizeof(s))
#define lowbit(x)                   ((x) &-(x))
#define IOS                         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl                        "\n"
typedef pair<int, int>               pii;
typedef pair<ll, ll>                 pll;
namespace prime_sieve_mu{
    const int N = 5e4 + 5;
    int  cnt, ans, prime[N], mu[N], sum[N], pre[N];
    bool flag[N];
    inline void init(){
        memset(flag, 1, sizeof(flag));
        flag[1] = 0;
        mu[1] = 1;
        cnt = 0;
        for(int i = 2; i <= N; i++)
        {
            if(flag[i]){
                prime[++cnt] = i;
                pre[i] = cnt;
                mu[i] = -1;
            }
            for(int j = 1; j <= cnt && 1ll * prime[j] * i <= N; j++){
                flag[prime[j] * i] = 0;
                if(i % prime[j] == 0) {
                    mu[prime[j] * i] = 0;
                    break;
                }
                else{
                    mu[prime[j] * i] = -mu[i];
                }
            }
        }
        for(int i = 1; i <= N; i++) {
            sum[i] = sum[i - 1] + mu[i];
        }
    }
}
using namespace prime_sieve_mu;
int a, b, c, d, k, n;

ll solve(int a, int b){
    a /= k; b /= k;
    int tmp = min(a, b);
    ll ans = 0;
    for(int l = 1, r; l <= tmp; l = r + 1){
        r = min(a / (a / l), b / (b / l));
        ans += (1ll) * (a / l) * (b / l) * (sum[r] - sum[l - 1]);
    }
    return ans;
}

int main()
{
    scanf("%d", &n);
    init();
    while(n --){
        cin >> a >> b >> c >> d >> k;
        printf("%lld\n", solve(b, d) - solve(a - 1, d) - solve(c - 1, b) + solve(a - 1, c - 1)); 
    }
    return 0;
}

P3327 [SDOI2015]约数个数和

传送门：https://www.luogu.com.cn/problem/P3327

求 $\sum_{i = 1} ^ n\sum_{j = 1} ^ m d(ij)$

首先有个前置知识 $d(ij) = \sum_{x|i}\sum_{y|j} [gcd(x,y)==1]$

好了，我们可以推式子了 $\begin{aligned} \sum_{i = 1} ^ n\sum_{j = 1} ^ m d(ij) &= \sum_{i = 1} ^ n\sum_{j = 1} ^ m \sum_{x|i}\sum_{y|j} [gcd(x,y)==1]\\ &= \sum_{i = 1} ^ n\sum_{j = 1} ^ m \sum_{x|i}\sum_{y|j} [gcd(x,y)==1] \\ &ps:我们知道\sum_{x|i}上限是n，\sum_{y|j}上限是m，但先不写出来 \\ &= \sum_{i = 1} ^ n\sum_{j = 1} ^ m \sum_{x|i}\sum_{y|j} \sum_{k|i,k|j} μ(k) \\ & ps:更改枚举顺序，改为枚举k，枚举出的k的上限为n和m的最小值(tmp = min(n,m))，然后i和j的上限改变 \\ &= \sum ^ {tmp} _ {k=1}μ(k) \sum_{i = 1} ^ {\lfloor\frac{n}{k} \rfloor}\sum_{j = 1} ^ {\lfloor\frac{m}{k} \rfloor} \sum_{x|i}\sum_{y|j} \\& ps:更改枚举顺序，改为枚举i和j，套路和k一样 \\ &= \sum ^ {tmp} _ {k=1}μ(k) \sum _{x = 1} ^{\lfloor\frac{n}{k} \rfloor} \sum_{i = 1} ^ {\lfloor\frac{n}{xk} \rfloor}\sum _{y = 1} ^{\lfloor\frac{m}{k} \rfloor}\sum_{j = 1} ^ {\lfloor\frac{m}{yk} \rfloor} \\ &=\sum ^ {tmp} _ {k=1}μ(k) \sum _{x = 1} ^{\lfloor\frac{n}{k} \rfloor} \lfloor\frac{n}{xk} \rfloor\sum _{y = 1} ^{\lfloor\frac{m}{k} \rfloor}\lfloor\frac{m}{yk} \rfloor \\& 令 g(n) = \sum_{i = 1} ^ n\lfloor\frac{n}{i} \rfloor \\ &=\sum ^ {tmp} _ {k=1}μ(k) \ g(\lfloor\frac{n}{k} \rfloor) \ g(\lfloor\frac{m}{k} \rfloor) \end{aligned}$
可以看出后面这一坨 $g(\lfloor\frac{n}{k} \rfloor) \ g(\lfloor\frac{m}{k} \rfloor)$ 是可以整除分块+预处理的，那为什么上一题的 $\sum_{k=1} ^ {tmp}μ(k) \lfloor\frac{n}{kd} \rfloor\lfloor\frac{m}{kd} \rfloor$ 不用预处理？
因为上个题的这个式子是可以平推过去的，整除分块可以现求，而现在这个式子，每个 $k$ 的取值都会决定不同的整除分块的值，所以我们需要把从 $1 \to N$ 的整除分块值都求出来，到时候 $O(1)$ 带就行了。

最后， $\sum ^ {tmp} _ {k=1}μ(k) \ g(\lfloor\frac{n}{k} \rfloor) \ g(\lfloor\frac{m}{k} \rfloor)$ 这个式子其实也是可以整除分块的， $μ(k)$ 没用前缀和多可惜呀 ~~（滑稽）~~

#include<bits/stdc++.h>
using namespace std;
#define ll                          long long
#define ull                         unsigned long long
#define ld                          long double
#define db                          double
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define mset(s, _)                  memset(s, _, sizeof(s))
#define lowbit(x)                   ((x) &-(x))
#define IOS                         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl                        "\n"
typedef pair<int, int>               pii;
typedef pair<ll, ll>                 pll;
namespace prime_sieve_mu{
    const int N = 5e4 + 5;
    int  cnt, ans, prime[N], pre[N], mu[N];
    ll sum[N], f[N];
    bool flag[N];
    inline void init()
    {
        memset(flag, 1, sizeof(flag));
        flag[1] = 0;
        mu[1] = 1;
        cnt = 0;
        for(int i = 2; i <= N; i++)
        {
            if(flag[i])
            {
                prime[++cnt] = i;
                pre[i] = cnt;
                mu[i] = -1;
            }
            for(int j = 1; j <= cnt && 1ll * prime[j] * i <= N; j++)
            {
                flag[prime[j] * i] = 0;
                if(i % prime[j] == 0) {
                    mu[prime[j] * i] = 0;
                    break;
                }
                else{
                    mu[prime[j] * i] = -mu[i];
                }
            }
        }
        for(int i = 1; i <= N; i ++){
            sum[i] = sum[i - 1] + mu[i];
            for(int l = 1, r; l <= i; l = r + 1){
                r = i / (i / l);
                f[i] += (1ll) * (r - l + 1) * (i / l);
            }
        }
    }
}
using namespace prime_sieve_mu;
int t, n, m;
int main()
{
    init();
    scanf("%d", &t);
    while(t --){
        scanf("%d%d", &n, &m);
        int tmp = min(n, m);
        ll ans = 0;
        for(int l = 1, r; l <= tmp; l = r + 1){
            r = min(n / (n / l), m / (m / l));
            ans += (1ll) * (sum[r] - sum[l - 1]) * f[n / l] * f[m / l];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

杜教筛

定义：杜教筛是以低于线性的时间复杂度来计算积性函数的前缀和的神奇筛法

需要计算的式子： $S(n) = \sum_{i = 1} ^ nf(i) \ ( f(i)为积性函数）$

为了解决这个问题，我们构造两个积性函数 $h$ 和 $g$ 。使得 $h=f ∗ g$

$\begin{aligned} \sum_{i = 1} ^ n h(i)&= \sum_{i = 1} ^ n (f*g)(i) \\ &=\sum_{i = 1} ^ n \sum_{d|i} g(d) f( \frac{i}{d}) \\ &= \sum_{d = 1} ^n g(d)\sum_{i=1} ^{\lfloor \frac{n}{d} \rfloor} f( \frac{i}{d}) \\ &ps:我们将右边式子的第一项给提出来 \\ &= g(1)×S(n) + ∑_{d=2} ^n g(d)×S(⌊\frac{n}{d}⌋) \\ &\to g(1)×S(n)=\sum_{i = 1} ^ n h(i) - ∑_{d=2} ^n g(d)×S(⌊\frac{n}{d}⌋) \end{aligned}$
基本式子我们这就推出来了，重点是如何选择正确的 $h$ 与 $g$ ，只要

$h(i)$ 前缀和很好求
$g(i)$ 容易整除分块

那么当我们对后面的式子进行整除分块时，求 $S(n)$ 的复杂度为 $O(n ^ {\frac{2}{3}})$

比如：

求 $S(n) = \sum_{i = 1} ^ nμ(i)$
- 根据式子 $g(1)×S(n)=\sum_{i = 1} ^ n h(i) - ∑_{d=2} ^n g(d)×S(⌊\frac{n}{d}⌋)$ ，我们需要找 $h$ 和 $g$ 满足 $μ* g = h$
- 翻到狄利克雷卷积那一节扫一眼， $μ * I = ε$ ， $μ * id = φ$ ，明显 $ε$ 的前缀和好求，就是 $1$ 嘛， $I$ 也容易分块。
- 则 $h = ε$ ， $g = I$ ，带入便得 $S(n) = 1 - ∑_{d=2} ^n S(⌊\frac{n}{d}⌋)$
求 $S(n) = \sum_{i = 1} ^ nφ(i)$
就不给出推导过程了。 $φ * I = id$
$S(n) = \sum_{i = 1} ^ n i - ∑_{d=2} ^n S(⌊\frac{n}{d}⌋)$

$\sum_{i = 1} ^ n i$ 可以通过等差数列 $O(1)$ 得到。
求
(逛博客时发现大佬给的例子，像下面这种一眼看不出结果的式子) $S(n) = \sum_{i = 1} ^ n i × φ(i)$
- 既然一眼看不出 $g$ 和 $h$ 是什么，那么我们可以先写出狄利克雷卷积： $∑_{d|n}(d⋅φ(d))×g(\frac{n}{d})$
- 我们当然希望 $d$ 可以消掉，正巧有个 $\frac{n}{d}$ ，那么就可以这么配了 $\begin{aligned} ∑_{d|n}(d⋅φ(d))×g(\frac{n}{d}) &= ∑_{d|n}(d⋅φ(d))×\frac{n}{d} \\ &=n × ∑_{d|n}φ(d) \\&= n^2 \end{aligned}$
  那么 $h(n) = n^2$ , $g = id$
  $S(n) = \sum_{i = 1} ^ n i ^2 - ∑_{d=2} ^n d × S(⌊\frac{n}{d}⌋)$

P4213 【模板】杜教筛（Sum）

传送门：https://www.luogu.com.cn/problem/P4213

#include<bits/stdc++.h>
using namespace std;
#define ll                          long long
#define ull                         unsigned long long
#define ld                          long double
#define db                          double
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define mset(s, _)                  memset(s, _, sizeof(s))
#define lowbit(x)                   ((x) &-(x))
#define IOS                         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl                        "\n"
typedef pair<int, int>               pii;
typedef pair<ll, ll>                 pll;

namespace prime_sieve_phi_mu{
    const int N = 6e6 + 5;
    int  cnt, ans, prime[N], pre[N], phi[N], mu[N];
    bool flag[N];
    ll sum_phi[N], sum_mu[N];
    inline void init()
    {
        memset(flag, 1, sizeof(flag));
        flag[1] = 0;
        cnt = 0;
        phi[1] = 1;
        mu[1] = 1;
        for(int i = 2; i <= N; i++){
            if(flag[i]){
                prime[++cnt] = i;
                pre[i] = cnt;
                phi[i] = i - 1;
                mu[i] = -1;
            }
            for(int j = 1; j <= cnt && 1ll * prime[j] * i <= N; j++){
                flag[prime[j] * i] = 0;
                if(i % prime[j] == 0) {
                    phi[i * prime[j]] = phi[i] * prime[j];
                    mu[prime[j] * i] = 0;
                    break;
                }
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
                mu[prime[j] * i] = -mu[i];
            }
        }
        for(int i = 1; i <= N; i++){
            sum_phi[i] = sum_phi[i - 1] + phi[i];
            sum_mu[i] = sum_mu[i - 1] + mu[i];
        }
    }
}
using namespace prime_sieve_phi_mu;

unordered_map < ll, ll > phi_w; //算过的一定要记录下来
unordered_map < ll, ll > mu_w;

ll djs_phi(ll x){
    if(x <= N) return sum_phi[x];
    if(phi_w[x]) return phi_w[x];
    ll ans = x * (x + 1) / 2;
    for(ll l = 2, r; l <= x; l = r + 1){
        r = x / (x / l);
        ans -= (r - l + 1) * (djs_phi(x / l));
    }
    return phi_w[x] = ans;
}

ll djs_mu(ll x){
    if(x <= N) return sum_mu[x];
    if(mu_w[x]) return mu_w[x];
    ll ans = 1;
    for(ll l = 2, r; l <= x; l = r + 1){
        r = x / (x / l);
        ans -= (r - l + 1) * (djs_mu(x / l));
    }
    return mu_w[x] = ans;
}

int t;
ll n;
int main()
{
    init();
    scanf("%d", &t);
    while(t --){
        scanf("%lld", &n);
        printf("%lld %lld\n", djs_phi(n), djs_mu(n));
    }
    return 0;
}

至此入门就结束了，最近碰到了个好题，正好写一下。

phi and phi

传送门：https://ac.nowcoder.com/acm/contest/10845/F

求 $\sum_{i=1} ^ n\sum_{j=1} ^ n φ(ij)φ(gcd(i,j))$
~~愉快地推柿子~~

很多结论在前面我都 $cue$ 到了，如果又看不懂的地方，可以翻到前面偷偷看一眼。 $\begin{aligned} \sum_{i=1} ^ n\sum_{j=1} ^ n φ(ij)φ(gcd(i,j)) &= \sum_{i=1} ^ n\sum_{j=1} ^ n \frac{φ(i)×φ(j)}{φ(gcd(i,j))} ×φ(gcd(i,j)) × gcd(i,j) \\ &= \sum_{i=1} ^ n\sum_{j=1} ^ n φ(i)×φ(j) × gcd(i,j) \\ & ps:将gcd(i,j) \to [gcd(i,j)==1] \\ &ps:这里相当于枚举d，把d提出来，φ里的系数要乘d \\ &= \sum_{d=1} ^{min(n,n)}d \sum_{d|i} ^ n\sum_{d|j} ^ n φ(di)×φ(dj) × [gcd(i,j) == 1] \\ &= \sum_{d=1} ^{n}d \sum_{i=1} ^ {\lfloor\frac{n}{d} \rfloor}\sum_{j=1} ^ {\lfloor\frac{n}{d} \rfloor} φ(di)×φ(dj) × [gcd(i,j) == 1] \\ &= \sum_{d=1} ^{n}d \sum_{i=1} ^ {\lfloor\frac{n}{d} \rfloor}\sum_{j=1} ^ {\lfloor\frac{n}{d} \rfloor} φ(di)×φ(dj) × \sum_{k|i,k|j} μ(k) \\ &= \sum_{d=1} ^{n}d \sum_{k=1} ^ {\lfloor\frac{n}{d} \rfloor} μ(k)\sum_{i=1} ^ {\lfloor\frac{n}{kd} \rfloor}\sum_{j=1} ^ {\lfloor\frac{n}{kd} \rfloor} φ(dki)×φ(dkj) \\ &= \sum_{d=1} ^{n}d \sum_{k=1} ^ {\lfloor\frac{n}{d} \rfloor} μ(k)(\sum_{i=1} ^ {\lfloor\frac{n}{kd} \rfloor}φ(dki))^2 \\ &令 T = kd \\&ps: 改为枚举T \\ &= \sum_{d=1} ^{n}d \sum_{k=1} ^ {\lfloor\frac{n}{d} \rfloor} μ(k)(\sum_{i=1} ^ {\lfloor\frac{n}{kd} \rfloor}φ(dki))^2 \\ &= \sum_{d=1} ^{n}d \sum_{kd=1} ^ {n} μ(k)(\sum_{i=1} ^ {\lfloor\frac{n}{kd} \rfloor}φ(dki))^2 \\ &ps:这里\sum_{d=1} ^{n} \to \sum_{d|T},比如T=4，那么就三种组合，(k=1,d=4),(k=2,d=2),(k=4,d=1)，可以看出两者作用相同 \\ &= \sum_{T=1} ^ {n} \sum_{d|T}d×μ(\frac{T}{d})(\sum_{i=1} ^ {\lfloor\frac{n}{T} \rfloor}φ(Ti))^2 \\ &= \sum_{T=1} ^ {n} φ(T)(\sum_{i=1} ^ {\lfloor\frac{n}{T} \rfloor}φ(Ti))^2 \\ & 设f(\frac{n}{T}) = \sum_{i=1} ^ {\lfloor\frac{n}{T} \rfloor}φ(Ti) \\&= \sum_{T=1} ^ {n} φ(T)[f(\frac{n}{T})]^2 \end{aligned}$
是不是很麻烦？
那我们不用 $μ$ 的性质，用的 $φ$ 的再试一遍！！ $\begin{aligned} \sum_{i=1} ^ n\sum_{j=1} ^ n φ(ij)φ(gcd(i,j)) &= \sum_{i=1} ^ n\sum_{j=1} ^ n \frac{φ(i)×φ(j)}{φ(gcd(i,j))} ×φ(gcd(i,j)) × gcd(i,j) \\ &= \sum_{i=1} ^ n\sum_{j=1} ^ n φ(i)×φ(j) × gcd(i,j) \\ &= \sum_{i=1} ^ n\sum_{j=1} ^ n φ(i)×φ(j) × \sum_{d|i,d|j} φ(d) \\ &= \sum_{d=1}^n φ(d)\sum_{i=1}^ {\lfloor\frac{n}{d} \rfloor}\sum_{j=1} ^ {\lfloor\frac{n}{d} \rfloor}φ(di)×φ(dj) \\&=\sum_{d=1}^n φ(d) (\sum_{i=1}^ {\lfloor\frac{n}{d} \rfloor}φ(di))^2 \\ & 设f(\frac{n}{d}) = \sum_{i=1} ^ {\lfloor\frac{n}{d} \rfloor}φ(di) \\&= \sum_{d=1} ^ {n} φ(d)[f(\frac{n}{d})]^2 \end{aligned}$
是不是这个简单多了！

但题目要求的是 $1 \to n$ 的所有值。
在枚举 $T$ 时， $n$ 在 $[i∗T,(i+1)∗T)$ 之间时，相当于整除分块的思想， $\frac{n}{T}$ 值都一样， $φ(T)[f(\frac{n}{T})]^2$ 的贡献不变。
所以对 $i*T$ 做一个差分，最后再求一个前缀和即可。

#include<bits/stdc++.h>
using namespace std;
#define ll                          long long
#define ull                         unsigned long long
#define ld                          long double
#define db                          double
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define mset(s, _)                  memset(s, _, sizeof(s))
#define lowbit(x)                   ((x) &-(x))
#define IOS                         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl                        "\n"
typedef pair<int, int>               pii;
typedef pair<ll, ll>                 pll;

const int mod = 1e9 + 7;
int mul(int x, int y){return 1ll * x * y % mod;}
int dec(int x, int y){return x >= y ? x - y : x + mod - y;}
int add(int x, int y){return x + y >= mod ? x + y - mod : x + y;}
namespace prime_sieve_phi{
    const int N = 5e6 + 6;
    int  cnt, prime[N], pre[N], phi[N];
    bool flag[N];
    inline void init()
    {
        memset(flag, 1, sizeof(flag));
        flag[1] = 0;
        cnt = 0;
        phi[1] = 1;
        for(int i = 2; i <= N; i++)
        {
            if(flag[i])
            {
                prime[++cnt] = i;
                pre[i] = cnt;
                phi[i] = i - 1;
            }
            for(int j = 1; j <= cnt && 1ll * prime[j] * i <= N; j++)
            {
                flag[prime[j] * i] = 0;
                if(i % prime[j] == 0) {
                    phi[i * prime[j]] = phi[i] * prime[j];
                    break;
                }
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            }
        }
    }
}
using namespace prime_sieve_phi;
int n;
ll ans[N];
int main()
{
    init();
    cin >> n;
    for(int T = 1;T <= n; T++) {
        ll sum = 0;
        for(int i = 1;i <= n / T; i++) {
            sum = add(sum, phi[i * T]);
            ans[i * T] = add(ans[i * T], mul(phi[T], mul(sum, sum)));
            ans[(i + 1) * T] = dec(ans[(i + 1) * T], mul(phi[T], mul(sum, sum)));
        }
    }
    for(int i = 1;i <= n; i++) {
        ans[i] = add(ans[i], ans[i - 1]);
        printf("%lld\n",ans[i]);
    }
    return 0;
}

完结。

#学习路径#