bzoj4454:C Language Practice(数论)

Author Avatar
Sakits 4月 06, 2018

题解

  GCD黑科技…O(1)O(1)GCD…
  设M=nM=\sqrt{n},可以用递推求出(i,j)\forall (i,j),满足i,jMi,j\leq Mgcd(i,j)gcd(i,j)
  黑科技基于这样一个定理:

 任意一个数xx,它一定能分解成三个数a,b,ca,b,c,满足每个数要么M\leq M,要么是质数。

 证明:设a>Ma>Maa为合数,那么bc<Mbc<M,且aa可以分解为a1,a2a_1,a_2,不妨设a1>a2a_1>a_2,那么这三个数又可以组成a1,a2,bca_1,a_2,bc,若a1>Ma_1>M且为合数,那么按上方步骤继续分解就一定能分出一种方案了。

  于是我们只需要求出每个数xx的最小质因子pp,把x÷px\div p分解式的最小项乘上pp即可得到xx的分解式,易证。
  询问gcd(x,y)gcd(x,y)的时候,对xx分解出的每一个数与yygcdgcd后合并:
    11.若xax_a为质数,则xyx|ygcd(xa,y)=xagcd(x_a,y)=x_a,否则gcd(xa,y)=1gcd(x_a,y)=1
    22.若xax_a为合数,那么xa,y mod xaxx_a,y\ mod\ x_a \leq \sqrt{x},由预处理的g[xa][y mod xa]g[x_a][y\ mod\ x_a]即可得到gcd(xa,y)gcd(x_a,y)

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define ll long long
#define int unsigned int
using namespace std;
const int maxn=1000010, inf=1e9, mx=1e6;
int n, m, T, cntp;
int a[2010], b[2010], f[maxn][3], g[1010][1010], pri[100010], p[maxn];
inline void read(int &k)
{
	k=0; char c=getchar();
	while(c<'0' || c>'9') c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
} 
inline int getgcd(int x, int y){return (x && y)?g[y][x%y]:x|y;}
inline void getpri()
{
	p[1]=1;	
	for(int i=2;i<=mx;i++)
	{
		if(!p[i]) pri[++cntp]=i, p[i]=i;
		for(int j=1;pri[j]*i<=mx;j++)
		{
			p[pri[j]*i]=pri[j	];
			if(i%pri[j]==0) break;
		}
	}
}
inline void init()
{
	getpri();
	f[1][0]=f[1][1]=f[1][2]=1;
	for(int i=2;i<=mx;i++)
	{
		memcpy(f[i], f[i/p[i]], sizeof(f[i]));
		if(f[i][0]*p[i]<=1000) f[i][0]*=p[i];
		else if(f[i][1]*p[i]<=1000) f[i][1]*=p[i];
		else f[i][2]*=p[i];
	}
	for(int i=0;i<=1000;i++)
	{
		for(int j=0;j<=i;j++)
		g[i][j]=g[j][i]=getgcd(i, j);
	}
}
inline int gcd(int x, int y)
{
	if(x<=1000 && y<=1000) return g[x][y];
	if(!x || !y) return x|y;
	int ans=1;
	for(int i=0;i<=2;i++)
	if(f[x][i]>1)
	{
		int t=f[x][i];
		if(p[t]==t) 
		{
			if(y%t) continue;
			y/=t; ans*=t;
		}
		else 
		{
			int d=g[t][y%t];
			y/=d; ans*=d;
		}
	}
	return ans;
}
#undef int
int main()
{
	#define int unsigned int
	init(); read(T);
	while(T--)
	{
		read(n); read(m);
		for(int i=0;i<n;i++) read(a[i]);
		for(int i=0;i<m;i++) read(b[i]);
		int ans=0;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			ans+=gcd(a[i], b[j])^i^j;
		}
		printf("%u\n", ans);
	}
}