差别

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

--- 2020-2021:teams:legal_string:王智彪:数论 [2021/09/23 23:36]
王智彪创建
+++ 2020-2021:teams:legal_string:王智彪:数论 [2021/09/25 19:16] (当前版本)
王智彪
@@ 行 139: / 行 139: @@
 </hidden>
+===== $Pollard Rho$ =====
+时间复杂度 $O(n^{\frac {1} {4}})$ ，用来找到 $n$ 的一个素因子 $p$ ，每次找到就一直除它，最不利的情况是每个素因子都是一次幂，所以全部分解的复杂度正常是 $O(n^{\frac {1} {4}}logn)$ 的，但因为质因数越多的时候大小都不一样，正常的对数级别的最后实际上也就是常数级别的影响，所以完全分解也可以看作是 $O(n^{\frac {1} {4}})$ 的。
+==== 例 $2$ ====
+=== 题目 ===
+[[https://nanti.jisuanke.com/t/42544]]
+给 $t$ 组数据 $(t≤8)$ ，每组数据给一个 $n,x,y,n≤10^{5},2≤x,y≤10^{18}$ ，代表一个长度为 $n$ 的数组 $a_{i},a_{i}≤10^{18}$ ，且保证 $a_{i}$ 之和小于 $y$ 。现在定义 $Z={\prod_{i=1}^{n}}a_{i}!$ 。求最大的 $i$ ，使得 $(Z×X^{i})|Y!$ 。
+=== 题解 ===
+显然对着一堆阶乘使劲是不可以的，显然 $Y!$ 可以约掉 $Z$ 所有的因子。剩下看 $X$ 都有什么因子，然后提前处理出 $Y!$ 和 $Z$ 中这些因子的幂次，做一个差，然后取所有剩余幂次/一个 $X$ 中有多少个幂次，就是能取多少个 $X$ ，然后取最小值就是答案。而 $X$ 的质因数分解，显然需要 $pollard_rho$ 。
+竟然一遍过了 $×$ 。
+<hidden 代码>
+<code cpp>
+#include <bits/stdc++.h>
+#define ll __int128
+using namespace std;
+ll maxv;
+inline ll quick_mul(ll a,ll b,ll p) {
+	unsigned long long c=(long double) a/p*b;
+	ll ret=a*b-(unsigned long long)c*p;
+	ret%=p;
+	while(ret<0) ret+=p;
+	return ret%p;
+}
+inline ll quick_power(ll a,ll b,ll p) {
+	ll ret=1;
+	while(b) {
+		if(b&1) ret=quick_mul(ret,a,p);
+		a=quick_mul(a,a,p);
+		b>>=1;
+	}
+	while(ret<0) ret+=p;
+	return ret%p;
+}
+bool check(ll a,ll n,ll x,ll t) {
+	ll ans=quick_power(a,x,n);
+	ll aans=ans;
+	for(int i=1; i<=t; i++) {
+		ans=quick_mul(ans,ans,n);
+		if(ans==1&&aans!=1&&aans!=n-1) return true;
+		aans=ans;
+	}
+	if(ans!=1) return true;
+	return false;
+}
+bool Miller_Rabin(ll n) {
+	if(n<2) return false;
+	if(n==2) return true;
+	if(!(n&1)) return false;
+	ll x=n-1,t=0;
+	while(!(x&1)) {
+		x>>=1;
+		t++;
+	}
+	for(int i=0; i<8; i++) { //8为测试次数
+		ll a=rand()%(n-1)+1;
+		if(check(a,n,x,t)) return false;
+	}
+	return true;
+}
+ll factor[1010],num;
+ll gcd(ll x,ll y) {
+	if(!x) return y;
+	if(!y) return x;
+	if(x<0) x=-x;
+	if(y<0) y=-y;
+	ll t=__builtin_ctzll(x|y);
+	x>>=__builtin_ctzll(x);
+	do {
+		y>>=__builtin_ctzll(y);
+		if(x>y) swap(x,y);
+		y-=x;
+	} while(y);
+	return x<<t;
+}
+ll pollard_rho(ll x,ll c) {
+	ll ci=1,k=2;
+	srand(time(NULL));
+	ll x0=rand()%(x-1)+1;
+	ll y=x0,t=1;
+	while(1) {
+		ci++;
+		x0=(quick_mul(x0,x0,x)+c)%x;
+		t=quick_mul(y-x0,t,x);
+		if(!t||!(y^x0)) return x;
+		if(ci==k) {
+			ll d=gcd(t,x);
+			if(d!=1) return d;
+			y=x0;
+			k<<=1;
+		}
+	}
+}
+void findfac(ll n,ll k) {
+	if(n==1) return;
+	if(Miller_Rabin(n)) {
+		factor[++num] = n;
+		return;
+	}
+	ll p=n,c=k;
+	while(p>=n) {
+		p=pollard_rho(p,c--);
+	}
+	findfac(p,k);
+	findfac(n/p,k);
+}
+inline void read(ll &X) {
+	X = 0;
+	int w=0;
+	char ch=0;
+	while(!isdigit(ch)) {
+		w|=ch=='-';
+		ch=getchar();
+	}
+	while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
+	if (w) X = -X;
+}
+void print(ll x) {
+	if (!x) return ;
+	if (x < 0) putchar('-'),x = -x;
+	print(x / 10);
+	putchar(x % 10 + '0');
+}
+ll n,x,y,a[100100];
+ll tmpfac[10010],tmps,tmpnum[10010];
+ll js[100100][17],zs[17];
+int main() {
+	int t;
+	scanf("%d",&t);
+	while(t--) {
+		num=0;
+		tmps = 0;
+		read(n);
+		read(x);
+		read(y);
+		for(int i=1; i<=n; i++) {
+			read(a[i]);
+		}
+		findfac(x,324757);
+		sort(factor+1,factor+num+1);
+		ll las=factor[1];
+		tmpfac[++tmps] = las;
+		tmpnum[tmps]=1;
+		for(int i=2; i<=num; i++) {
+			if(factor[i]==las) {
+				tmpnum[tmps]++;
+			} else {
+				las = factor[i];
+				tmpfac[++tmps] = factor[i];
+				tmpnum[tmps] = 1;
+			}
+		}
+		for(int i=1; i<=tmps; i++) {
+			for(int j=1; j<=n; j++) {
+				ll ansss=0;
+				ll kkk = tmpfac[i];
+				for(ll k=a[j]; k; k=k/kkk) {
+					ansss+=k/kkk;
+				}
+				js[j][i]=ansss;
+			}
+		}
+		for(int i=1; i<=tmps; i++) {
+			for(int j=2; j<=n; j++) js[1][i] += js[j][i];
+		}
+		for(int i=1; i<=tmps; i++) {
+			ll ansss=0;
+			ll kkk = tmpfac[i];
+			for(ll k=y; k; k=k/kkk) {
+				ansss+=k/kkk;
+			}
+			zs[i] = ansss;
+		}
+		for(int i=1;i<=tmps;i++) zs[i]-=js[1][i];
+		ll maxv=1e18;
+		for(int i=1;i<=tmps;i++) {
+			maxv=min(maxv,zs[i]/tmpnum[i]);
+		}
+		if(maxv) print(maxv);
+		else putchar('0');
+		putchar('\n');
+	}
+	return 0;
+}
+</code>
+</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

用户工具

站点工具

差别

页面工具