[HDU] 2020中国大学生程序设计竞赛(CCPC) - 网络选拔赛 Lunch
考虑\(SG\)定理:
\[\begin{cases} SG(S)=\text{mex}\{SG(T) \mid S \Rightarrow T\} \\ SG(S)=\oplus_{i} SG(w_i)(\cup_{i}w_i=S \land \cap_{i}w_i=\emptyset) \end{cases} \]记得sort之后unique
打完表之后,可以发现SG的值跟质因数的次数和有关
排除一下边界问题后,可以得到:SG(i) = i的奇质因子个数 + [i是偶数]
#include
using namespace std;
int SG(int n) {
if(n == 1) {
return 0;
}
vector p;
for(int i = 2 ; i <= n ; ++ i) {
if(n % i == 0) {
int t = SG(n / i);
if(i & 1) {
p.push_back(t);
} else {
p.push_back(0);
}
}
}
sort(p.begin(), p.end());
unique(p.begin(), p.end());
int i, j;
for(i = 0, j = 0 ; j < p.size() ; ++ i, ++ j) {
if(i != p[j]) break;
}
return i;
}
// SG(i) = i的奇质因子个数 + [i是偶数]
int main() {
// freopen("data.in", "w", stdout);
// for(int i = 1 ; i <= 1000 ; ++ i) {
// int sg = SG(i);
// if(sg == 1 || i % 2 != 0) continue;
// printf("SG(%d) = %d ", i, sg);
// for(int j = 2, t = i ; j <= t ; ++ j) {
// if(t % j == 0) {
// int tot = 0;
// while(t % j == 0) t /= j, ++ tot;
// printf(" %d^%d + ", j, tot);
// }
// }
// puts("");
// }
const int M = 1e5;
vector pri, vis(M + 10);
for(int i = 2 ; i <= M ; ++ i) {
if(!vis[i]) {
for(int j = i ; j <= M ; j += i) {
vis[j] = 1;
}
pri.push_back(i);
}
}
int t; scanf("%d", &t);
while(t --) {
int n; cin >> n;
int sg = 0;
while(n --) {
int x; scanf("%d", &x);
if(x == 1) continue;
if(x == 2) {
sg ^= 1;
continue;
}
int tot = x % 2 == 0;
for(auto p: pri) {
if((long long) p * p > x) break;
if(x % p == 0) {
int cnt = 0;
while(x % p == 0) x /= p, ++ cnt;
if(p != 2) {
tot += cnt;
}
}
}
if(x > 1) ++ tot;
sg ^= tot;
}
puts(sg ? "W" : "L");
}
}