欧拉函数

• 相关文章

欧拉函数：

即 $\phi (n)$，表示的是小于等于 $n$ 和 $n$ 互质的数的个数。

${\displaystyle \phi (i)=\sum _{i=1}^n[gcd(i,n)=1]}$

性质：

• 欧拉函数是积性函数。如果有 $gcd(a,b)=1$，那么 $\phi (a\times b)=\phi (a)\times \phi (b)$。特别地，当 $n$ 是奇数时 $\phi (2n)=\phi (n)$。

• $n=\sum _{d\mid n}\phi (d)$。

• 若 $n=p^k$，其中 $p$ 是质数，那么 $\phi (n)=p^k-p^{k-1}$。 （根据定义可知）

• 由唯一分解定理，设 $n=\prod _{i=1}^s{p}_i^{k_i}$，其中$p_i$ 是质数，有 $\phi (n)=n\times \prod _{i=1}^s{\displaystyle \frac{p_i-1}{p_i}}$。

实现：

一个数的欧拉函数值:

#include <cmath>

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

筛法求欧拉函数值 :

有：
$\phi (n)=n\times \prod _{i=1}^s{\displaystyle \frac{p_i-1}{p_i}}$

${\displaystyle \phi (i)=\sum _{i=1}^n[gcd(i,n)=1]}$

在线性筛的基础上修改：

vector<int> minp, primes, phi;

void sieve(int n) {
    minp.assign(n + 1, 0);
    phi.assign(n + 1, 0);
    primes.clear();
	phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
            phi[i] = i - 1;
        }

        for (auto p : primes) {
            if (i * p > n) break;
            minp[i * p] = p;
            if (p == minp[i]) {
                phi[i * p] = phi[i] * p;
                break;
            } 
            phi[i * p] = phi[i] * phi[p];
        }
    }
}

练习题

P2568 GCD

给定正整数 $n$，求 $1\le x,y\le n$ 且 $gcd(x,y)$ 为素数的数对 $(x,y)$ 有多少对。

即求 ${\displaystyle \sum _{i=1}^n\sum _{j=1}^n[gcd(i,j)=p]}$

$⟹{\displaystyle \sum _{p\in prims}(2\sum _{i=1}^{n/p}\phi (i)-1)}$

#define int long long
vector<int> minp, primes, phi;
signed main() {
    int n;cin >> n;
    sieve(n);
    phi[1] = 1;
    partial_sum(phi.begin(), phi.end(), phi.begin());
    int ans = 0;
    for (auto p : primes) {
        ans += 2 * phi[n / p] - 1;
    }
    cout << ans << '\n';
}

P2398 GCD SUM

求 ${\displaystyle \sum _{i=1}^n\sum _{j=1}^{n}gcd(i,j)}$

对于 $gcd(x,y)=1\to gcd(xk,yk)=k$

$gcd(x,y)=k$ 的个数为 ${\displaystyle 2\sum _{i=1}^{n/k}\phi (i)-1}$

所以遍历一遍 $k\to$ $gcd(i,j)=k$ 的情况即可。

#define int long long
signed main() {
    int n;cin >> n;
    sieve(n);
    partial_sum(phi.begin(), phi.end(), phi.begin());
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        ans += i * (2 * phi[n / i] - 1);
    }
    cout << ans << '\n';
}

P2158 仪仗队

题目满足 $gcd(\left|x-x^{\prime }\right|,\left|y-y^{\prime }\right|)=1$，有 $(x^{\prime },y^{\prime })=(1,1)$

则 $gcd(x-1,y-1)=1$，求 $(x,y)$ 对数，即可以先将 $x,y$ 减去 1 (相当于将坐标向右上方移动了一位)，然后多出的 $(1,0),(0,1)$ 特判一下，则答案就是：

$⟹{\displaystyle 2+2\times (\sum _{i=1}^{n-1}\phi (i)-1)=2\times \sum _{i=1}^{n-1}\phi (i)+1}$

#define int long long
signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;cin >> n;
    sieve(n);
    if (n == 1) {
        cout << "0\n";return 0;
    }
    partial_sum(phi.begin(), phi.end(), phi.begin());
    cout << phi[n - 1] * 2 + 1 << '\n';
}

欧拉定理：

内容：若 $gcd(a,m)=1$，则 $a^{\phi (m)}\equiv 1(\mathrm{mod}m)$。

费马小定理可以看作当$m$ 是质数 $p$ 时欧拉定理的一个特殊情形。

扩展欧拉定理:

扩展欧拉定理内容：