> 文章列表 > 【数学】02:欧拉函数

【数学】02:欧拉函数

【数学】02:欧拉函数

欧拉函数


OVERVIEW

  • 欧拉函数
      • 一、欧拉函数
        • 1.定义欧拉函数
        • 2.欧拉函数练习
          • (1)AcWing873.欧拉函数
          • (2)AcWing874.筛法求欧拉函数
      • 二、快速
        • 1.快速幂
        • 2.快速幂练习
          • (1)AcWing875.快速幂
          • (2)AcWing876.快速幂求逆元
      • 三、扩展欧几里得算法
        • 1.扩展欧几里得算法练习
          • (1)AcWing877.扩展欧几里得算法
          • (2)AcWing878.线性同余方程
      • 四、中国剩余定理
        • 1.中国剩余定理练习
          • (1)AcWing204.表达整数的奇怪方式

一、欧拉函数

1.定义欧拉函数

  • 欧拉函数定义:1~n中与n互质的数的个数,例φ(6)=2φ(6) = 2φ(6)=2
  • 如果 N=p1α1∗p2α2∗....∗pnαnN = p1^{α1}*p2^{α2}*....*pn^{αn}N=p1α1p2α2....pnαn
  • 则有公式:φ(N)=N∗(1−1p1)(1−1p2)...(1−1pn)φ(N) = N*(1-\\frac{1}{p1})(1-\\frac{1}{p2})...(1-\\frac{1}{pn})φ(N)=N(1p11)(1p21)...(1pn1)
  • 时间复杂度:O(n)=nO(n) = \\sqrt{n}O(n)=n

在这里插入图片描述

2.欧拉函数练习

(1)AcWing873.欧拉函数

对于每一个数字,分别从定义出发求其欧拉函数:

#include<iostream>
using namespace std;int main() {int m; cin >> m;while (m--) {int num; cin >> num;int res = num;//最后结果//1.分解质因数for (int i = 2; i <= num / i; ++i) {if (num % i == 0) {/* i为num的一个因子 */    res = res / i * (i - 1);//res = res * (1 - 1/i);公式内容while (num % i == 0) num /= i;}}//2.说明num有一个大于1的质因数if (num > 1) res = res / num * (num - 1);cout << res << endl;}return 0;
}
  • 注意:在 res = res / num * (num - 1)中, 不能写成 res = res * (num - 1) / num;顺序不可颠倒
(2)AcWing874.筛法求欧拉函数

如果需要求出1~N中,每一个数字的欧拉函数,这时再使用公式法(将每个数都分解质因数)将导致时间复杂度为O(n)=nnO(n) = n\\sqrt{n}O(n)=nn

在筛法求素数的过程中,计算出每一个数的欧拉函数:

#include<iostream>
#include<algorithm>
using namespace std;const int MAX = 1000010;int primes[MAX], cnt;//质数数组、质数下标
bool st[MAX];//每个数字是否已经被筛选掉int phi[MAX];long long get_eulers(int n) {/* 线性筛法过程中 顺便将欧拉函数求一遍 */phi[1] = 1;for (int i = 2; i <= n; ++i) {if (!st[i]) {primes[cnt++] = i;//质数添加phi[i] = i - 1;}for (int j = 0; primes[j] <= n / i; ++j) {st[primes[j] * i] = true;//进行筛选if (i % primes[j] == 0) {//优化为线性的phi[primes[j] * i] = phi[i] * primes[j];//数学推导break;}phi[primes[j] * i] = phi[i] * (primes[j] - 1);//数学推导}}//计算总和long long res = 0;for (int i = 1; i <= n; ++i) res += phi[i];return res;
}int main() {int n; cin >> n;cout << get_eulers(n) << endl;return 0;
}
  • 欧拉定理:若a与n互质,则有 aφ(n)≡1(modn)a^{φ(~n~)}~≡1~(mod~n)aφ( n ) 1 (mod n)
  • 费马定理:当n为质数时,则有 ap−1≡1(modp)a^{~p-~1}~≡1~(mod~p)a p 1 1 (mod p)

二、快速幂

1.快速幂

快速幂的核心:反复平方法

快速幂即快速的求出 akmodpa^k~mod~pak mod p 的结果,可以在 O(logk)O(logk)O(logk) 的时间复杂度内求出结果,其中满足 1≤a,p,k≤1091~≤~a~,~p~,~k~≤~10^91  a , p , k  109

在这里插入图片描述

在这里插入图片描述

//暴力法O(k)
res = 1;
for (int i = 1; i <= k; ++i) {res = res * a % p;
}
//快速幂O(logk)
int res = 1;
while (k) {if (k & 1) res = (long long)res * a % p;k >>= 1;//最后一位抹去a = (long long)a * a % p;
}
return res;

2.快速幂练习

(1)AcWing875.快速幂
#include<iostream>
using namespace std;//a^k % p
int qmi(int a, int k, int p) {int res = 1;while (k) {if (k & 1) res = (long long)res * a % p;k >>= 1;//最后一位抹去a = (long long)a * a % p;}return res;
}int main() {int m;scanf("%d", &m);while (m--) {int a, k, p;scanf("%d%d%d", &a, &k, &p);printf("%d\\n", qmi(a, k, p));}return 0;
}
(2)AcWing876.快速幂求逆元
  • 考察:费马定理与快速幂
#include<iostream>
using namespace std;//a^k % p
int qmi(int a, int k, int p) {int res = 1;while (k) {if (k & 1) res = (long long)res * a % p;k >>= 1;//最后一位抹去a = (long long)a * a % p;}return res;
}int main() {int m;scanf("%d", &m);while (m--) {int a, p;scanf("%d%d", &a, &p);int res = qmi(a, p - 2, p);if (a % p) printf("%d\\n", res);//res != 0 表示a不是p的倍数else puts("impossible");//a是p的倍数}return 0;
}

三、扩展欧几里得算法

  • 裴蜀定理:对于任意正整数 a、ba、bab ,一定存在非零整数 x、yx、yxy ,使得 ax+by=(a,b)ax + by = (a, b)ax+by=(a,b) (最大公约数)

在这里插入图片描述

1.扩展欧几里得算法练习

(1)AcWing877.扩展欧几里得算法
#include<iostream>
using namespace std;// (a, b) = (b, a mod b)
// return b ? gcd(b, a % b) : a;
int gcd(int a, int b) {if (!b) return a;return gcd(b, a % b);
}// ax + by = (a, b)
int exgcd(int a, int b, int &x, int &y) {if (!b) {x = 1;y = 0;return a;}int d = exgcd(b, a % b, y, x);//递归求y -= a / b * x;return d;
}int main() {int m;scanf("%d", &m);while (m--) {int a, b, x, y;scanf("%d%d", &a, &b);exgcd(a, b, x, y);printf("%d %d\\n", x, y);}return 0;
}
(2)AcWing878.线性同余方程
  • 给定a、m、ba、m、bamb,求一个整数 xxx 使得 ax≡b(modm)ax~≡b~(mod~m)ax b (mod m)

在这里插入图片描述

#include<iostream>
using namespace std;// (a, b) = (b, a mod b)
// return b ? gcd(b, a % b) : a;
int gcd(int a, int b) {if (!b) return a;return gcd(b, a % b);
}// ax + by = (a, b)
int exgcd(int a, int b, int &x, int &y) {if (!b) {x = 1;y = 0;return a;}int d = exgcd(b, a % b, y, x);//递归求y -= a / b * x;return d;
}int main() {int m;scanf("%d", &m);while (m--) {int a, b, m;scanf("%d%d%d", &a, &b, &m);int x, y;int d = exgcd(a, m, x, y);if (b % d) puts("impossible");else printf("%d\\n", (long long)x * (b / d) % m);}return 0;
}

四、中国剩余定理

在这里插入图片描述

1.中国剩余定理练习

(1)AcWing204.表达整数的奇怪方式