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
|
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 (){
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("%dn",(ans+mod-2)%mod);
}
return 0;
}
|
近期评论