1006 GCD Game
#include<iostream> #include<cstring> #include<queue> #include<map> #include<set> #include<algorithm> #include<cmath> #include<vector> #define fi first #define se second #define lowbit(x) (x&-x) using namespace std; namespace ae86{ const int bufl=1<<15; char buf[bufl],*s=buf,*t=buf; inline int fetch(){ if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;} return*s++; } inline int read(){ int a=0,b=1,c=fetch(); while(!isdigit(c))b^=c=='-',c=fetch(); while(isdigit(c))a=a*10+c-48,c=fetch(); return b?a:-a; } } using ae86::read; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<int,double> pid; const int inf=0x3f3f3f3f; const ll INF=2e18; const double eps=1e-8; const double pi=acos(-1); const int mod=1e9+7; const int N=1000010; int T; int n; int a[N]; int primes[N*10],cnt[N*10]; bool st[N*10]; void get_primes(int n){ int tot=0; for(int i=2;i<=n;i++){ if(!st[i]) primes[tot++]=i,cnt[i]=1; for(int j=0;primes[j]<=n/i;j++){ st[primes[j]*i]=true; cnt[primes[j]*i]=cnt[i]+1; if(i%primes[j]==0) break; } } } int main(){ T=read(); get_primes(1e7); while(T--){ n=read(); int res=0; for(int i=1;i<=n;i++){ a[i]=read(); if(a[i]==1) continue; res^=cnt[a[i]]; } if(n==1&&a[1]==1) puts("Bob"); else if(n==1) puts("Alice"); else if(res) puts("Alice"); else puts("Bob"); } }