得到 cond get 每次 while %d mem sizeof void
题意:给定一个正整数序列,两人轮流对这个数列进行如下修改:选取一个素数p和一个整数k将序列中能整除p^k的数除以p^k,问谁有必胜策略。
借此复习一下sg函数吧,sg(x) = mex ( sg(y) |y是x的后继结点 )。我们不难发现不同的质因子是互不影响的,因此我们可以把不同的质因子归为不同的game。因为每次操作对整个序列有效,所以序列中p^k的个数也是不影响答案的。因此我们可以用一个二进制位表示当前序列是否存在p^k,如果存在,则其第(k-1)位为1。由是把所有game的sg异或起来即可得到答案。
- #include < bits / stdc++.h > using namespace std;#define MAXN 1000000 + 10 int n,
- tot = 0,
- flag = 0,
- prime[MAXN];
- bool is[MAXN];
- map < int,
- int > sg,
- st;
- int getsg(int x) {
- if (x == 0) return 0;
- if (sg.count(x)) return sg[x];
- map < int,
- int > vis;
- int p = x,
- t = 0;
- while (p) p >>= 1,
- t++;
- for (int i = 1; i <= t; i++) vis[getsg((x >> i) | (x & ((1 << i - 1) - 1)))] = 1;
- for (int i = 0;; i++) if (!vis[i]) return sg[x] = i;
- }
- void form() {
- memset(is, true, sizeof(is));
- is[1] = false;
- for (int i = 2; i <= MAXN - 5; i++) {
- if (is[i]) prime[++tot] = i;
- for (int j = 1; j <= tot && i * prime[j] <= MAXN - 5; j++) {
- is[i * prime[j]] = false;
- if (i % prime[j] == 0) break;
- }
- }
- }
- void deal(int x) {
- for (int i = 1; prime[i] * prime[i] <= x; i++) {
- int t = 0;
- while (x % prime[i] == 0) {
- x /= prime[i];
- t++;
- }
- if (t) st[prime[i]] |= 1 << (t - 1);
- }
- if (x != 1) st[x] |= 1;
- }
- int main() {
- form();
- scanf("%d", &n);
- for (int i = 1; i <= n; i++) {
- int x;
- scanf("%d", &x);
- deal(x);
- }
- map < int,
- int > ::iterator it;
- for (it = st.begin(); it != st.end(); it++) flag ^= getsg(it - >second);
- if (flag) printf("Mojtaba\n");
- else printf("Arpa\n");
- return 0;
- }
Codeforces 850C Arpa and a game with Mojtaba
来源: http://www.bubuko.com/infodetail-2357313.html