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

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

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

目录

一.欧拉函数

 二.欧拉函数模板

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

 四.快速幂

 五.扩展欧几里得算法

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

---

一.欧拉函数

 即有一个数n， n通过质因数分解得到

通过欧拉函数有

证明：容斥原理

 二.欧拉函数模板

实际上就是分解质因数

时间复杂度：O()

//计算一个数的欧拉函数的值
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(), 用遍历每个数的方法来求每个数欧拉函数时间复杂度是O(),用筛法求每个数的欧拉函数只需要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;
}

 

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

---