P9401 [POI2020 R3] Kolekcjoner Bajtemonów 2 题解

_•́へ•́╬_ · 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);
}