设最大权值为\(M\)

\(T=\sqrt M\)

定理

任意一个\(\le M\)的数一定可以表示为abc三个数的乘积

满足这三个数要么\(\le T\)，要么是一个质数

证明：

考虑反证

假设\(a>b>c\)，满足\(a>T\)且\(a\)不为素数

因为\(a>T\)且\(abc\le M\)，则有\(bc\le T\)

我们设\(a=x*y\),一定不可能x,y均\(\ge T\)

假设\(x>y\),则\(y \le T\)

则原数可表示为\(x,y,bc\)三数乘积

若此时x仍不满足两条件之一，继续分解，最后定能满足

预处理O(n)

线性筛，求出每个数的最小质因子
预处理每个数能分解成哪三个数

对于x,其最小质因数为p

则x的分解先复制\(x/p\)的分解

设为a,b,c

若\(a*p\le T\)则\(a*=p\)

若\(b*p\le T\)则\(b*=p\)

否则\(c*=p\)

正确性证明：

不难发现若\(p\ge T\)则x为素数且x=p

而对于x为素数的,\(x/p=1\)显然正确，不用考虑

那么此时\(p\le T\)

若a,b,c其一为1,显然正确，不用考虑

此时有\(a*p,b*p,c*p\)均为合数

所以：现在要证明的是\(a,b,c\)中至少有一个数乘\(p\)后\(\le T\)

就是证明\(a,b,c\)中不会出现每一个数乘\(p\)都\(\ge T\)

反证：

根据条件有\(a,b,c>\frac T p\)

设\(x/p\)的最小质因数为w，则\(w\ge p\)

依此类推\(a,b,c\ge p\)

①\(p< \sqrt T\)，此时\(a,b,c>\sqrt T\)

\(pabc>\frac {T^3} {p^2}>{T^2}=M\)

说明原数在权值范围M之外，矛盾

②\(p\ge \sqrt T\)，

此时\(pabc>p^4>T^2=M\)
预处理T以内两两数的gcd

可以递推,像辗转相除,g[x][y]=g[y][x%y]

Code

void init_gcd(){

	notprime[1]=1;

	int i,j,d;

	for(i=2;i<N;i++){

		if(!notprime[i]){

			prime[++cnt]=i;

			p[i]=i;

		}

		for(j=1;j<=cnt;j++){

			if((LL)prime[j]*i>=N) break;

			d=prime[j]*i;

			notprime[d]=1;

			p[d]=prime[j];

			if(i%prime[j]==0) break;

		}

	}

	split[1][0]=split[1][1]=split[1][2]=1;

	for(i=2;i<N;i++){

		memcpy(split[i],split[i/p[i]],sizeof(split[i/p[i]]));

		if(split[i][0]*p[i]<=sn) split[i][0]*=p[i];

		else if(split[i][1]*p[i]<=sn) split[i][1]*=p[i];

		else split[i][2]*=p[i];

	}

	// gcd(0,0)=0 , gcd(0,x)=x

	for(i=0;i<=sn;i++)

	for(j=0;j<=i;j++){

		if(!i||!j) g[i][j]=i|j;

		else g[i][j]=g[j][i]=g[j][i%j];//j<=i

	}

}

求两数gcd O(1)

int gcd(int x,int y){

	int ans=1,i,d;

	for(i=0;i<3;i++){

		if(split[x][i]<=sn) d=g[split[x][i]][y%split[x][i]];

		else d=(y%split[x][i]==0)?split[x][i]:1;

		ans*=d;

		y/=d;//避免算重

	}

	return ans;

}

巴特西

O(1)gcd学习笔记

定理

预处理O(n)

Code

求两数gcd O(1)

最新文章

热门文章