问题 A: x

时间限制: 1 Sec 内存限制: 256 MB

题面

题面谢绝公开。

题解

赛时想到了正解并且对拍了很久。对拍没挂，但是评测姬表示我w0了……一脸懵逼。

不难证明，如果对于两个数字$i,j$，$gcd_{i,j}>1$的话，那么这两个数字必定分在一组内，否则不满足条件。

因此考虑对每一个数字质因数分解。包含同一质因数的数字不能分在同一集合。

此时只需用并查集维护集合个数。最后统计集合分配即可。

注意：每一个1都可以单独分配在一个集合里使得答案满足条件。因此每一个1都应单独放在一个集合中。特判即可。

另外，直接质因数分解会T掉。事先筛一遍素数即可。（用了最慢的筛法，实测可过）

#include<bits/stdc++.h>

#define int long long

#define rint register int

#define read(A) A=init()

#define mod 1000000007

using namespace std;

inline int init()

{

    int a=,b=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')b=-;ch=getchar();}

    while(ch>=''&&ch<=''){a=(a<<)+(a<<)+ch-'';ch=getchar();}

    return a*b;

}

int ToT,n,a[],sum,prime[],tot;

int cnt,cp[],pc[],fa[];

bool vis[],isnt[];

vector <int> v[];

inline int get_fa(int x){return (fa[x]==x)?x:fa[x]=get_fa(fa[x]);}

inline int gcd(int A,int B){return (B==)?A:gcd(B,A%B);}

inline void I_get()

{

    for(rint i=;i<=;++i)

    {

        if(!isnt[i])

        {

            prime[++tot]=i;int lin=;

            while(lin*i<=)isnt[lin*i]=,lin++;

        }

    }

}

inline int qpow(int x,int y)

{

    int num=;

    while(y)

    {

        if(y&)num=num*x%mod;

        x=x*x%mod;y>>=;

    }

    return num;

}

inline void merge(int x,int y)

{

    int fx=get_fa(x);

    int fy=get_fa(y);

    if(fx!=fy)sum--,fa[fy]=fx;

    return ;

}

inline void Devide(int id)

{

    int x=a[id];

    for(rint i=;prime[i]<=sqrt(x);++i)

    {

        if(x%prime[i]==)

        {

            x/=prime[i];while(x%prime[i]==)x/=prime[i];

            if(!vis[prime[i]])

            {

                vis[prime[i]]=;cp[++cnt]=prime[i];pc[prime[i]]=cnt;

                v[cnt].clear();

                v[cnt].push_back(id);

            }

            else v[pc[prime[i]]].push_back(id);

        }

    }

    if(x>)

    {

        if(!vis[x])

        {

            vis[x]=;cp[++cnt]=x;pc[x]=cnt;

            v[cnt].clear();

            v[cnt].push_back(id);

        }

        else v[pc[x]].push_back(id);

    }

    return ;

}

signed main()

{

    read(ToT);I_get();

    while(ToT--)

    {

        read(n);sum=n;

        cnt=;

        memset(vis,,sizeof(vis));

        for(rint i=;i<=n;++i)

        {

            read(a[i]);fa[i]=i;

            if(a[i]!=)Devide(i);

        }

        for(rint i=;i<=cnt;++i)

        {

            int lin=v[i][];

            for(rint j=;j<v[i].size();++j)

                merge(lin,v[i][j]);

        }

        printf("%lld\n",(qpow(,sum)-+mod)%mod);

        continue;

    }

}

巴特西

「题解」：x

问题 A: x

题面

题解

最新文章

热门文章