题意
Alice和Bob玩游戏。
给定一个数N。初始M=1。每轮操作要求从N的素因子中选一个数p出来，然后M=M*p。最后一轮使得M=N的人获胜。M大于N，平局。
解题
因为1e12差不多接近了2^31，所以先对[1,1e6]的范围打一个素数表。
根据这个素数表，对N进行质因数分解。
分解后的结果有三种情况：
（1）有三个及以上的质因子。这时肯定打平。
（2）有两个质因子。这时看这两个质因子出现的次数，分别设为x和y。如果x=y，先手输。x-y=1，先手赢。x-y>1,平局。
（3）一个质因子。奇数个则先手赢，否则先手输。
AC代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <string>using namespace std;
const int maxn=1e6+7;
int ans[maxn+1],tot;
bool valid[maxn+1];
int a[maxn+1],b[maxn+1];void getPrime(int n)
{memset(valid,true,sizeof(valid));for(int i=2;i<=n;i++){if(valid[i]){tot++;ans[tot]=i;}for(int j=1;j<=tot && i*ans[j]<=n;j++){valid[i*ans[j]]=false;if(i%ans[j]==0) break;}}
}
int main()
{int T;scanf("%d",&T);char name[20];tot=0;getPrime(maxn);while(T--){int x;int cnt=0;scanf("%d %s",&x,name);for(int i=1; i<=tot; i++){if(x%ans[i]==0){a[++cnt]=ans[i];b[cnt]=0;if(cnt>=3){break;}while(x%ans[i]==0){++b[cnt];x/=ans[i];}}}if(x!=1){a[++cnt]=x;b[cnt]=1;}if(cnt>=3) printf("tie\n");else if(cnt==1){if(b[cnt]&1) printf("%s\n",name[0]=='A'?"Alice":"Bob");else printf("%s\n",name[0]=='A'?"Bob":"Alice");}else{if(abs(b[1]-b[2])>1) printf("tie\n");else if(abs(b[1]-b[2])==1) printf("%s\n",name[0]=='A'?"Alice":"Bob");else printf("%s\n",name[0]=='A'?"Bob":"Alice");}}return 0;
}