差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:王智彪:数论 [2021/09/24 18:10]
王智彪
+++ 2020-2021:teams:legal_string:王智彪:数论 [2021/09/25 19:16] (当前版本)
王智彪
@@ 行 140: / 行 140: @@
 </hidden>
-===== Pollard Rho =====
+===== $Pollard Rho$ =====
 时间复杂度 $O(n^{\frac {1} {4}})$ ，用来找到 $n$ 的一个素因子 $p$ ，每次找到就一直除它，最不利的情况是每个素因子都是一次幂，所以全部分解的复杂度正常是 $O(n^{\frac {1} {4}}logn)$ 的，但因为质因数越多的时候大小都不一样，正常的对数级别的最后实际上也就是常数级别的影响，所以完全分解也可以看作是 $O(n^{\frac {1} {4}})$ 的。
@@ 行 338: / 行 338: @@
 </hidden>
+===== 威尔逊定理 =====
+若 $p$ 为素数，则 $(p-1)!+1 ≡ p(mod p)$ 。
+===== 原根 =====
+如果 $a$ 模 $m$ 的阶等于 $\phi(m)$ ，则称 $a$ 为模 $m$ 的一个原根。素数一定有原根，原根不唯一，部分合数也有原根。
+$1000000007$ 的原根为 $5$ 。
+$998244353$ 的原根为 $3$ 。
+===== 最大公约数和最小公倍数 =====
+==== 求 n 的正约数集合 ====
+复杂度是 $O({\sqrt {n}})$ 的。
+<hidden 代码>
+<code cpp>
+vector<int>factor;
+int m;
+int main() {
+	scanf("%d", &n);
+	for(int i = 1; i * i <= n; ++ i) {
+		if(n % i == 0) {
+			factor.push_back(i);
+			if(i != n / i)
+				factor.push_back(n / i);
+		}
+	}
+	for(int i = 0; i < factor.size(); ++ i) {
+		printf("%d\n", factor[i]);
+	}
+	return 0;
+}
+</code>
+</hidden>
+==== 求 1…n 中每个数的正约数的集合 ====
+求 $1…n$ 中每个数的正约数的集合，算法复杂度 $O(nlogn)$ ，总数也是这个级别的。
+方法倍数法：类似于埃氏筛的思路，枚举倍数，如果能除开一定会被发现，并且因为每轮倍数不同，所以只发现一次。
+<hidden 代码>
+<code cpp>
+#include <bits/stdc++.h>
+#define ll long long
+using namespace std;
+int n;
+vector<int> factor[100100];
+int main() {
+	scanf("%d", &n);
+	n=100000;
+	for(int i = 1; i <= n; ++ i) {
+		for(int j = 1 ; j * i <= n; ++ j) {
+			factor[i * j].push_back(j);
+		}
+	}
+	ll ans=0;
+	for(int i=1;i<=n;i++) {
+		ans+=factor[i].size();
+	}
+	printf("%lld\n",ans);
+	return 0;
+}
+</code>
+</hidden>
+==== 一些结论 ====
+$gcd(F(n),F(m))=F(gcd(n,m))$
+$gcd(a^{m}-1,a^{n}-1)=a^{gcd(n,m)}-1(a>1,n>0,m>0)$
+更进一步，有：
+$gcd(a^{m}-b^{m},a^{n}-b^{n})=a^{gcd(n,m)}-b^{gcd(n,m)}(gcd(a,b)=1)$
+设 $G=gcd(C(n,1),C(n,2),…,C(n,n-1))$
+.若 $n$ 为素数， $G=n$ ，因为分母不含 $p$ ，分子有 $p$ 。
+.$n$ 非素且有只有一个素因子 $p$ ， $G=p$ ， $n=p^{a}$ ，显然分母幂次小于分子幂次，取 $C(n,p^{a-1})$ ，可以证明分子只比分母多一次，所以 $G=p$ 。
+.$n$ 有多个素因子， $G=1$ ，将 $n$ 做质因数分解，设 $p_{1}$ 的幂次是 $a_{1}$ ，取 $C(n,p_{1}^{a_{1}})$ ，可以证明没有 $p_{1}$ 的幂次。同理也有没有 $p_{i}$ 幂次的数，所以所有的最大公约数是 $1$ 。
+$(n+1)lcm(C(n,0),C(n,1),…,C(n,n))=lcm(1,2,…,n+1)$
+$\sum_{i=1}^{n}gcd(i,n) = \sum_{d|n}d{\phi ({\frac {n} {d}})}$
+===== 斐波那契数列 =====
+前缀和： $\sum_{i=1}^{n}f_{i}=f_{n+2}-1$ 数学归纳法。
+奇数项前缀和： $\sum_{i=1}^{n}f_{2i-1}=f_{2n}$ 数学归纳法。
+偶数项前缀和：  $\sum_{i=1}^{n}f_{2i}=f_{2n+1}-1$ 数学归纳法。
+平方前缀和： $\sum_{i=1}^{n}f_{i}^{2}=f_{n}f_{n+1}$ 数学归纳法
+$f_{n+m}=f_{n-1}f_{m-1}+f_{n}f_{m}$
+$f_{n}^{2}=(-1)^{n-1}+f_{n-1}f_{n+1}$
+$f_{2n-1}=f_{n}^{2}-f_{n-2}^{2}$
+$f_{n}={\frac {f_{n+2}+f_{n-2}} {3}}$

CVBB ACM Team

用户工具

站点工具

差别

页面工具