数学知识--（欧拉函数，快速幂，扩展欧几里得算法）

本文主要是介绍数学知识--（欧拉函数，快速幂，扩展欧几里得算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文用于记录个人算法竞赛学习，仅供参考

一.欧拉函数

二.欧拉函数模板

三.用筛法求每个数的欧拉函数

四.快速幂

五.扩展欧几里得算法

六.用扩展欧几里得算法求线性同余方程

一.欧拉函数

即有一个数n， n通过质因数分解得到 $n=^{{_{\rho 1}}^{\alpha 1} \cdot {_{\rho 2}}^{\alpha 2} ... {_{\rho k}}^{\alpha k}}$

通过欧拉函数有 $\phi (n) = n(1-\frac{1}{\rho 1})(1-\frac{1}{\rho 2})...(1-\frac{1}{\rho k})$

证明：容斥原理

二.欧拉函数模板

$\phi (n) = n(1-\frac{1}{\rho 1})(1-\frac{1}{\rho 2})...(1-\frac{1}{\rho k})$

实际上就是分解质因数

时间复杂度：O( $n^{\frac{1}{2}}$ )

//计算一个数的欧拉函数的值
int phi(int x)
{int result = x;//分解质因数for (int i = 2; i <= x / i; i++){if (x % i == 0){//注意变形result = result / i * (i - 1);//将质数i除干净while (x % i == 0)x /= i;}}if (x > 1)result = result / x * (x - 1);return result;
}

三.用筛法求每个数的欧拉函数

求一个数的欧拉函数是O( $n^{\frac{1}{2}}$ ), 用遍历每个数的方法来求每个数欧拉函数时间复杂度是O( $n*n^{\frac{1}{2}}$ ),用筛法求每个数的欧拉函数只需要O(n)

//筛法求欧拉函数const int N = 100;
int primes[N], cnt; //primes存储素数，cnt用于计数
int eulers[N];       //存储每个数的欧拉函数
bool st[N];         //st判断该数是否被筛掉void get_eulers(int n)
{eulers[1] = 1;for (int i = 2; i <= n; i++){if (!st[i]){primes[cnt++] = i;eulers[i] = i - 1;}for (int j = 0; primes[j] <= n / i; j++){int t = primes[j] * i;st[t] = true;if (i % primes[j] == 0){eulers[t] = eulers[i] * primes[j];break;}eulers[t] = eulers[i] * (primes[j] - 1);}}
}

四.快速幂

//求 m^ k mod p，时间复杂度 O(logk)。int qmi(int m, int k, int p)
{int result = 1;int t = m;while (k){if (k & 1)result = result * t % p;t = t * t % p;k >>= 1;}return result;
}

五.扩展欧几里得算法

//扩展欧几里得算法
//ax + by = gcd(a,b),求x，y
//注意xy是&
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;
}

六.用扩展欧几里得算法求线性同余方程

//扩展欧几里得算法
//ax + by = gcd(a,b),求x，y
//注意xy是&
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 n;scanf("%d", &n);while (n--){int a, b, m;scanf("%d %d %d", &a, &b, &m);int x = 0, y = 0;int d = exgcd(a, m, x, y);if (b % d != 0)printf("impossible\n");elseprintf("%d\n", (b / d) * x % m);}return 0;
}

这篇关于数学知识--（欧拉函数，快速幂，扩展欧几里得算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！