O(1)gcd学习笔记

设最大权值为(M)
(T=sqrt M)

定理

任意一个(le M)的数一定可以表示为abc三个数的乘积
满足这三个数要么(le T)，要么是一个质数
证明：
考虑反证
假设(a>b>c)，满足(a>T)且(a)不为素数
因为(a>T)且(abcle M)，则有(bcle T)
我们设(a=x*y),一定不可能x,y均(ge T)
假设(x>y),则(y le T)
则原数可表示为(x,y,bc)三数乘积
若此时x仍不满足两条件之一，继续分解，最后定能满足

预处理O(n)

1. 线性筛，求出每个数的最小质因子

2. 预处理每个数能分解成哪三个数
   对于x,其最小质因数为p
   则x的分解先复制(x/p)的分解
   设为a,b,c
   若(a*ple T)则(a*=p)
   若(b*ple T)则(b*=p)
   否则(c*=p)
   正确性证明：
   不难发现若(pge T)则x为素数且x=p
   而对于x为素数的,(x/p=1)显然正确，不用考虑
   那么此时(ple 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，则(wge p)
   依此类推(a,b,cge p)
   ①(p< sqrt T)，此时(a,b,c>sqrt T)
   (pabc>frac {T^3} {p^2}>{T^2}=M)
   说明原数在权值范围M之外，矛盾
   ②(pge sqrt T)，
   此时(pabc>p^4>T^2=M)

3. 预处理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;
}