欧拉函数

Dec 16, 2024 11:43 AM
Dec 17, 2024 4:34 AM

欧拉函数:

φ(n),表示的是小于等于 nn 互质的数的个数。

φ(i)=i=1n[gcd(i,n)=1]

性质:

实现:

一个数的欧拉函数值:

#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;
}

筛法求欧拉函数值 :

有:
φ(n)=n×i=1spi1pi

φ(i)=i=1n[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];
        }
    }
}

练习题

给定正整数 n,求 1x,yngcd(x,y) 为素数的数对 (x,y) 有多少对。

即求 i=1nj=1n[gcd(i,j)=p]

pprims(2i=1n/pφ(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';
}

i=1nj=1ngcd(i,j)

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

gcd(x,y)=k 的个数为 2i=1n/kφ(i)1

所以遍历一遍 k 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';
}

题目满足 gcd(|xx|,|yy|)=1,有 (x,y)=(1,1)

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

2+2×(i=1n1φ(i)1)=2×i=1n1φ(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φ(m)1(modm)

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

扩展欧拉定理:

扩展欧拉定理内容:

ab{Abmodφ(m),gcd(a,m)=1,Ab,gcd(a,m)1,b<φ(m),A(bmodφ(m))+φ(m),gcd(a,m)1,bφ(m).(modm)