LINK

若存在$w[v]\%e[u]==0$

说明玩完游戏$u$马上可以玩游戏$v$,我们连上一条$u$到$v$的边

那么游戏能玩两次以上相当于在这个有向图中处于一个环,可以玩无限多次

直接上$tarjan$找环即可

但是这样连边是$O(n^2)$的,需要优化

我们建立一排虚点,分别表示数字$[1,100000]$

我们让游戏$i$向数字$e[i]$连边,数字$w[i]$向$i$连边

然后对于数字$v$向所有是$v$的倍数的数连边

这样如果存在$w[v]\%e[u]==0$

路径上是$u$到数字$e[u]$,再到数字$w[v]$,数字$w[v]$到$v$

在这个图上找环就好了

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e7+10;
const int base = 100001;
struct edge{
	int to,nxt;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v){ d[++cnt] = ( edge ){v,head[u]},head[u] = cnt; }
int low[maxn],dfn[maxn],vis[maxn],stac[maxn],top,id,scc,sd[maxn],num[maxn];
int n,w[maxn],e[maxn];
void tarjan(int u)
{
	dfn[u] = low[u] = ++id; stac[++top] = u; vis[u] = 1;
	for(int i=head[u];i;i=d[i].nxt )
	{
		int v = d[i].to;
		if( !dfn[v] )
		{
			tarjan(v);
			low[u] = min( low[u],low[v] );
		}
		else if( vis[v] )	low[u] = min( low[u],low[v] );
	}
	if( dfn[u]!=low[u] )	return;
	int temp; ++scc;
	while( temp = stac[top--] )
	{
		num[scc]++; sd[temp] = scc; vis[temp] = 0;
		if( temp==u )	break;
	}
}
int main()
{
	int t; cin >> t;
	while( t-- )
	{
		cin >> n;
		for(int i=1;i<=n;i++)	cin >> w[i];
		for(int i=1;i<=n;i++)	cin >> e[i];
		
		for(int i=1;i<=100000;i++)
		for(int j=i+i;j<=100000;j+=i)
			add(i+n,j+n);	
			
		for(int i=1;i<=n;i++)
			add(i,n+e[i]), add( n+w[i],i );
		for(int i=1;i<=n;i++)	if( !dfn[i] )	tarjan(i);
		int ans = 0;
		for(int i=1;i<=n;i++)
			if( num[sd[i]]>=2 || w[i]%e[i]==0 )	ans++;

		cout << ans << endl;
		
		for(int i=1;i<=n+base;i++)	head[i] = num[i] = dfn[i] = low[i] = 0;
		scc = id = top = 0; cnt = 1;
	}
}