自动搬运

查看原文

来自洛谷，原作者为

	•́へ•́╬ Unsuccessful Leaving Something attempt

搬运于2025-08-24 22:48:02，当前版本为作者最后更新于2023-06-07 11:58:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

首先可以全选 $b$。

如果选了任何一个 $a$，那么答案不会超过 $5\times 10^5$。考虑枚举这个答案。

结论：对于两对数，如果它们的 $a$ 相同，那么可以合并，新的 $b$ 为它们的 $b$ 的 $\gcd$。

理由：选一个 $a$ 一个 $b$ 肯定不优于选两个 $a$。

所以 $n\leq 10^6$ 是吓人的。

然后 ST 表随便维护一下就好了。

具体地，枚举答案，把非答案倍数的 $a$ 对应的 $b$，$\gcd$ 起来，如果得到的是答案的倍数，那就可行。

复杂度 $\mathcal O(a\log a)$。这里我没算 $\gcd$ 产生的 $\log$，因为位运算优化的 gcd 太 tm 快了。

code

#include<stdio.h>
#define N 500001
#define LG 19
#define min(x,y) ((x)<(y)?(x):(y))
#define abs(x) ((x)>>63?-(x):(x))
inline char nc()
{
	static char buf[99999],*l,*r;
	return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
	char c=nc();for(;c<'0'||'9'<c;c=nc());
	for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
inline void read(long long&x)
{
	char c=nc();for(;c<'0'||'9'<c;c=nc());
	for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int n,lg[N];long long a[N],tmp,st[LG][N],ans,gg;
inline long long gcd(long long x,long long y)
{
	if(!x||!y)return x|y;
	if(x==1||y==1)return 1;
	int cx=__builtin_ctzll(x),cy=__builtin_ctzll(y),z=min(cx,cy);
	y>>=cy;
	for(long long diff;x;
		x>>=cx,cx=__builtin_ctzll(diff=x-y),y=min(x,y),x=abs(diff));
	return y<<z;
}
inline void get(const int&l,const int&r)
	{int i=lg[r-l];ans=gcd(ans,st[i][l]);ans=gcd(ans,st[i][r-(1<<i)+1]);}
main()
{
	read(n);
	for(int x;n--;read(x),read(tmp),a[x]=gcd(a[x],tmp),gg=gcd(gg,tmp));
	for(int i=2;i<N;lg[i]=lg[i>>1]+1,++i);
	for(int i=1;i<N;st[0][i]=a[i],++i);
	for(int i=1;i<LG;++i)for(int j=1;j<N;++j)
		if(j+(1<<i-1)<N)st[i][j]=gcd(st[i-1][j],st[i-1][j+(1<<i-1)]);
		else st[i][j]=st[i-1][j];
	for(int i=N-1;i>gg;--i)
	{
		ans=0;get(1,i-1);
		if((N-1)%i)get((N-1)/i*i+1,N-1);
		for(int j=2;i*j<N&&!(ans%i);++j)get(i*(j-1)+1,i*j-1);
		if(!(ans%i)){printf("%d",i);return 0;}
	}
	printf("%lld",gg);
}