欧拉函数
欧拉函数
1.欧拉函数
欧拉函数定义：1~n中与n互质的数的个数，例$φ(6) = 2$
如果 $N = p1^{α1}p2^{α2}….*pn^{αn}$
则有公式：$φ(N) = N*(1-\frac{1}{p1})(1-\frac{1}{p2})…(1-\frac{1}{pn})$；
时间复杂度：$O(n) = \sqrt{n}$
2.AcWing873.欧拉函数对于每一个数字，分别从定义出发求其欧拉函数：
12345678910111213141516171819202122#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;顺序不可颠倒
3.AcWing874.筛法求欧拉函数如果需要求出1~N中，每一个数字的欧拉函数，这时再使用公式法 ...
快速幂
快速幂
1.快速幂快速幂的核心：反复平方法
快速幂即快速的求出 $a^kmodp$ 的结果，可以在 $O(logk)$ 的时间复杂度内求出结果，其中满足 $1≤a,p,k≤10^9$，
12345//暴力法O(k)res = 1;for (int i = 1; i <= k; ++i) { res = res * a % p;}
12345678//快速幂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;
1.AcWing875.快速幂123456789101112131415161718192021222324#include<iostream>using namespace std;//a^k % pint 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.快速幂求逆元
考察：费马定理与快速幂
1234567891011121314151617181920212223242526#incl ...
扩展欧几里得算法
扩展欧几里得算法
裴蜀定理：对于任意正整数 $a、b$ ，一定存在非零整数 $x、y$ ，使得 $ax + by = (a, b)$ （最大公约数）
1.AcWing877.扩展欧几里得算法123456789101112131415161718192021222324252627282930313233#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、b$，求一个整数 $x$ 使得 $ax≡b(mod~m)$
1234567891011121314151617181920212223242526272829303132333435#include<iostream>using namespace std;// (a, b) = (b, a mod ...