数学知识

欧拉函数

欧拉函数 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 ...

整数除法 原题链接：https://leetcode.cn/problems/xoh6Oh/ 编程语言可能会提供占据不同内存空间的整数类型，每种类型能表示的整数范围不同， 无符号整数无论二进制表示的最高位是0还是1，其都表示一个正数，32位整数的范围为 ~ 。由于整数范围的限制，如果计算结果超出了范围，就会产生溢出。产生溢出时运行不会出错，但是计算结果可能会出乎意料。 1.减法主要思路：为了求得dividend/divisor，可以不断的从dividend里减去divisor，当不能再减去更多的divisor时，循环执行的次数就是商 存在问题： 当除数很大时，减法操作执行的次数就会很多，导致程序超时，如 没有考虑除数与被除数，在32位int数据类型的范围溢出问题 没有考虑除法结果，在32位int数据类型的范围溢出问题 12345678910111213141516class Solution {public: int divide(int dividend, int divisor) { int flag = 0; int count = 0; if (dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0) flag = 1; dividend = abs(dividend); divisor = abs(divisor); while (dividend - divisor >= 0) { dividend -= divisor; count++; } if (flag) count = -count; return count; }}; 2.减法的优化主要思路： 当被除数大于除数时，继续比较判断被除数是否大于除数的2倍，如果是则继续判断是否大于除数的4倍、8倍、… 倍， 如果被除数最多大于除数的 倍，则将被除数减去除数的 倍，然后将剩余的被除数重复前面的步骤（由于每次 ...

Multiples of 3 and 5 If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000. 1.枚举123456789101112#include <iostream>using namespace std;int main(){ int ans = 0; //时间复杂度:O(n) for(int i = 1; i < 1000; i++){ if(i % 3 == 0 || i % 5 == 0) ans += i; } cout << ans << endl; return 0;} 2.前n项求和公式思路：3或5的倍数之和 = 3的倍数之和 + 5的倍数之和 - 15的倍数之和（减去重复计入值） 1234567891011#include <iostream>using namespace std;int main(){ //时间复杂度:O(4) int t3 = (3 + 999) * 333 / 2; int t5 = (5 + 995) * 199 / 2; int t15 = (15 + 990) * 66 / 2; cout << t3 + t5 - t15 <<endl; return 0;}