学步园

题目大意：给你n个数，问你有多少种选法，使得选出来的数，两两不是互质勾股数对   a,b是互质勾股数对当且仅当gcd(a,b)==1 且 存在整数c使得 a^2+b^2=c^2  n<=1000000,数字大小<=1000000

这题比较神，而且复杂度比较蛋疼

具体来说，这题首先把是互质勾股数对的连边，不是在给你的数字上连，是直接在1~1000000上连

然后每个点给你一个CNT，代表这个点可以被选几次，这样就变成求独立集的个数了

求独立集个数的话，每个连通块分开做，就先找出每个环上的一条边，把它断掉，在暴力枚举这些边有关的点，在暴力枚举这些点选或不选，剩下的就可以当树做了

找互质勾股数对，可以先枚举一个n，m当n，m不同奇偶且gcd(n,m)==1 时 m^2-n^2 与 2*m*n 构成互质勾股数对  这样就可以了

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define sqr(x) (1LL*(x)*(x))
using namespace std;
const int maxh=1000011,maxm=300011<<1,mod=1000000007;
inline int gcd(int a,int b){while (b) b^=a^=b^=a%=b;return a;}
inline int read(){
    char ch=getchar();int x=0;
    while (!isdigit(ch)) ch=getchar();
    for (;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return x;
}
int cnt[maxh],n,POW2[maxh];
int tot=0,pre[maxm],son[maxm],now[maxh];
void add(int a,int b){pre[++tot]=now[a];now[a]=tot;son[tot]=b;}
void cc(int a,int b){
    if (!cnt[a] || !cnt[b]) return;add(a,b);add(b,a);
}
void prepare(){
    POW2[0]=1;for (int i=1;i<=n;++i) POW2[i]=2*POW2[i-1]%mod;
    for (int n=1;1LL*n*n<maxh;++n) for (int m=n+1;2LL*n*m<maxh;++m)
        if (sqr(m)-sqr(n)<maxh && (n&1)!=(m&1) && gcd(n,m)==1) cc(sqr(m)-sqr(n),2*n*m);
}
void init(){tot=0;n=read();for (int i=1;i<=n;++i) ++cnt[read()];}
bool vis[maxh],mark[maxh],must[maxh];int q[maxh],fa[maxh];
struct xx{
    int a,b;
    xx(){}
    xx(int a_,int b_){a=a_;b=b_;}
}e[maxm];
int etot,N;
void bfs(int x){
    static int head,tail;
    for (head=0,tail=1,q[1]=x,fa[x]=0,vis[x]=1;head<tail;)
        for (int p=now[q[++head]];p;p=pre[p]) if (son[p]!=fa[q[head]] && cnt[son[p]])
            if (!vis[son[p]]) fa[q[++tail]=son[p]]=q[head],vis[son[p]]=1;
                else mark[son[p]]=mark[q[head]]=1,e[++etot]=xx(son[p],q[head]),son[p]=0;
    N=tail;
}
int f[maxh][2];
void TreeDp(int x){
    if (!x) return;
    f[x][0]=1;f[x][1]=POW2[cnt[x]]-1;if (mark[x]) f[x][must[x]^1]=0;
    for (int p=now[x];p;p=pre[p]) if (cnt[son[p]] && son[p]!=fa[x]){
        TreeDp(son[p]);
        f[x][0]=(1LL*f[x][0]*(f[son[p]][0]+f[son[p]][1]))%mod;
        f[x][1]=(1LL*f[x][1]*f[son[p]][0])%mod;
    }
}
int p[maxh];
inline void Add(int &a,int &b){a+=b;if (a>mod) a-=mod;}
void dfs(int dep,int n,int &res){
    if (dep>n){
        for (int i=1;i<=etot;++i) if (must[e[i].a] && must[e[i].b]) return;
        TreeDp(q[1]);if (mark[q[1]]) Add(res,f[q[1]][must[q[1]]]);else Add(res,f[q[1]][0]),Add(res,f[q[1]][1]);
        return;
    }
    must[p[dep]]=1;dfs(dep+1,n,res);
    must[p[dep]]=0;dfs(dep+1,n,res);
}
int solve(int x){
    etot=0;int ptot=0;bfs(x);
    for (int i=1;i<=N;++i) if (mark[q[i]]) p[++ptot]=q[i];
    int res=0;dfs(1,ptot,res);
    return res;
}
void work(){
    prepare();int ans=1;
    for (int i=1;i<maxh;++i) if (cnt[i] && !vis[i]) ans=1LL*ans*solve(i)%mod;
    printf("%d\n",ans-1);
}
int main(){
    init();
    work();
//  for (;;);
    return 0;
}