欧拉函数

\(phi_x\) 表示 \(1\) 到 \(x\) 中的所有与 \(x\) 互质的数字数量

性质：

• x为质数时，\(phi_x = x - 1\)，\(phi_{x^2} = p ^ 2 - p\)，…… \(phi_{x^k} = p ^ k - p ^ {k - 1} = (p - 1) \times p ^ {k - 1}\)
• 当 \(a, b\) 互质时，\(phi_{a \times b} = phi_a * phi_b\)

做法:

F1:

适用点：数据规模大，数组存不下
直接枚举 \(x\) 的每一个因子，暴力 \(O(\sqrt{x})\)

int val(int x) {
  int tmp = 1;
  for (int i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      tmp *= (i - 1);
      x /= i;
      while (x % i == 0) {
      tmp *= i;
      x /= i;
      }
    }
  }
  if (x != 1) {
    tmp *= (x - 1);
  }
  return tmp;
}

F2:

适用点：多次数据
在欧拉筛中处理

cin >> n;
phi[1] = 1;
for (int i = 2; i < N; i++) {
  if (!vis[i]) {
    p.push_back(i);
    phi[i] = i - 1;
  }
  for (auto j : p) {
    if (j * i >= N) {
      break;
    }
    vis[i * j] = true;
    if (i % j == 0) {
      phi[i * j] = phi[i] * j;
      break; 
    }
    phi[i * j] = phi[i] * (j - 1);
  }
}

整数分块

当你要求 \(\sum\limits_{i=1}^{n} n \div i\)
你可以发现：
\(20\div1 = 20\)
\(20\div2 = 10\)
\(20\div3 = 6\)
\(20\div4 = 5\)
\(20\div5 = 4\)
\(20\div6 = 3\)
\(20\div7 = 2\)
\(20\div8 = 2\)
\(20\div9 = 2\)
\(20\div10 = 2\)
\(20\div11 = 1\)
\(20\div12 = 1\)
\(20\div13 = 1\)
\(20\div14 = 1\)
\(20\div15 = 1\)
\(20\div16 = 1\)
\(20\div17 = 1\)
\(20\div18 = 1\)
\(20\div19 = 1\)
\(20\div20 = 1\)
显然，有许多重复的值，代码：

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