2021“MINIEYE杯”中国大学生算法设计超级联赛（8）- 1006（GCD Game）

2021“MINIEYE杯”中国大学生算法设计超级联赛（8）- 1006（GCD Game）

补题链接：​​>^<

题解思路可参考​

​​code​​

#include using namespace std;const int N = 1e7 + 10;typedef long long ll;bool st[N];int primes[N], cnt, sg[N];void init(){ st[0] = 1; st[1] = 1; for (int i = 2; i < N; ++i) { if(!st[i]) { primes[cnt++] = i; sg[i] = 1; } for (int j = 0; primes[j] <= (N-1) / i; ++j) { st[primes[j] * i] = true; sg[i * primes[j]] = sg[i] + 1; if(i % primes[j] == 0){ break; } } }}int main(){ int t, n, a; ll sum; init(); scanf("%d", &t); while(t--){ scanf("%d", &n); sum = 0; for (int i = 1; i <= n; ++i) { scanf("%d", &a); if(a == 1) continue; sum ^= sg[a]; } if(sum){ printf("Alice\n"); }else{ printf("Bob\n"); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。