【2018-国庆雅礼-NOIP-培训】-D4T1-x

发表于

题面

这里有链接

题解

这题咋一看好像是数论，实际上数论的成分不多qwq，但还是比较水的。

首先将 gcd ̸= 1 的连边，求连通块个数，若个数为 cnt，那么答案为 2cnt −2。

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+10,maxa=1e6+10,mod=1e9+7;
int t,n,last[maxa],ans;
bool vis[maxn];
vector<int> g[maxn];
int pcnt,prime[maxa],minp[maxa];
bool prm[maxa];

inline void init(){
	for(int i=2;i<maxa;++i){
		if(!prm[i]){
			prime[++pcnt]=i;
			minp[i]=i;
		}
		for(int j=1;j<=pcnt&&i*prime[j]<maxa;++j){
			prm[i*prime[j]]=true;
			minp[i*prime[j]]=prime[j];
			if(i%prime[j]==0)
				break;
		}
	}
}
void dfs(int pos){
	vis[pos]=true;
	for(int i=0;i<g[pos].size();++i)
		if(!vis[g[pos][i]])
			dfs(g[pos][i]);
}

int main(){
	freopen("x.in","r",stdin);
	freopen("x.out","w",stdout);
	init();
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=pcnt;++i)
			last[prime[i]]=0;
		for(int i=1,x;i<=n;++i){
			vis[i]=false;
			g[i].clear();
			scanf("%d",&x);
			while(x>1){
				int fac=minp[x];
				while(x%fac==0)
					x/=fac;
				if(last[fac]){
					g[i].push_back(last[fac]);
					g[last[fac]].push_back(i);
				}
				last[fac]=i;
			}
		}
		ans=1;
		for(int i=1;i<=n;++i)
			if(!vis[i])
				ans=ans*2%mod,dfs(i);
		printf("%d\n",(ans+mod-2)%mod);
	}
	return 0;
}