D一种因子游戏

思路：我们考虑，对于A数组中的每个数，我们考虑B数组中是否存在某个对应的数字能和其匹配，即$gcd$等于1。由此想到二分图最大匹配，算出最大匹配数然后判断即可。

#include<bits/stdc++.h>using namespace std;
const int N=2e6+5;
typedef long long ll;
typedef pair<ll,ll> pll;
int mod=1e9+7;
const int maxv=4e6+5;
const double pi=acos(-1.0);vector<int> e[N];
int st[N];
int f[N];bool dfs(int x)
{for(auto u : e[x]){if(st[u]) continue;st[u]=1;if(!f[u]||dfs(f[u])){f[u]=x;return true;}}return false;
}void solve()
{	int n;cin>>n;vector<int> a(n+5),b(n+5);//vector<int >st(n+5);for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int x=__gcd(a[i],b[j]);if(x==1){e[i].push_back(j);}}}int ans=0;for(int i=1;i<=n;i++){memset(st,0,sizeof st);if(dfs(i)) ans++;}//  cout<<ans<<endl;if(ans<n){cout<<"Alice"<<endl;}else cout<<"Bob"<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;//ol();//cin>>t;while(t--){solve();}system("pause");return 0;
}