結果

問題 No.1881 Everything is the same...
ユーザー 👑 hos.lyrichos.lyric
提出日時 2022-03-18 23:19:28
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 4,372 bytes
コンパイル時間 2,099 ms
コンパイル使用メモリ 133,436 KB
実行使用メモリ 13,884 KB
最終ジャッジ日時 2024-04-14 11:33:14
合計ジャッジ時間 5,992 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
13,884 KB
testcase_01 AC 3 ms
6,940 KB
testcase_02 AC 3 ms
6,944 KB
testcase_03 AC 3 ms
6,940 KB
testcase_04 AC 3 ms
6,944 KB
testcase_05 AC 3 ms
6,940 KB
testcase_06 AC 30 ms
6,944 KB
testcase_07 AC 5 ms
6,944 KB
testcase_08 AC 5 ms
6,940 KB
testcase_09 AC 4 ms
6,940 KB
testcase_10 TLE -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
testcase_50 -- -
testcase_51 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


int root(vector<int> &uf, int u) {
  return (uf[u] < 0) ? u : (uf[u] = root(uf, uf[u]));
}
bool connect(vector<int> &uf, int u, int v) {
  u = root(uf, u);
  v = root(uf, v);
  if (u == v) return false;
  if (uf[u] > uf[v]) swap(u, v);
  uf[u] += uf[v];
  uf[v] = u;
  return true;
}


int M;
vector<bool> oks;
map<vector<bool>, int> cache;

int calc(vector<bool> fs) {
  vector<int> uf(M, -1);
  for (int a = 1; a < M; ++a) if (fs[a]) {
    for (int u = 0; u < M; ++u) {
      connect(uf, u, (Int)u * a % M);
    }
  }
  for (int a = 1; a < M; ++a) if (root(uf, 1) == root(uf, a)) {
    fs[a] = true;
  }
  
  auto it = cache.find(fs);
  if (it != cache.end()) {
    return it->second;
  }
  
  set<int> app;
  set<int> used;
  for (int a = 1; a < M; ++a) if (oks[a] && !fs[a]) {
    if (used.insert(root(uf, a)).second) {
      auto gs = fs;
      gs[a] = true;
      const int res = calc(gs);
      app.insert(res);
    }
  }
  
  int ret = -1;
  for (int g = 0; ; ++g) {
    if (!app.count(g)) {
      ret = g;
      break;
    }
  }
  return cache[fs] = ret;
}


int brute(int m) {
  M = m;
  oks.assign(m, false);
  for (int a = 1; a < m; ++a) {
    oks[a] = (__gcd(m, a) == 1);
  }
  cache.clear();
  vector<bool> start(m, false);
  return calc(start);
}


constexpr int LIM = 100'010;
int lpf[LIM];

map<int, vector<int>> mg(int m) {
  map<int, vector<int>> pess;
  for (; m > 1; ) {
    const int p = lpf[m];
    int e = 0;
    do {
      ++e;
      m /= p;
    } while (m % p == 0);
    if (p == 2) {
      if (e == 1) {
        //
      } else if (e == 2) {
        pess[2].push_back(1);
      } else {
        pess[2].push_back(1);
        pess[2].push_back(e - 2);
      }
    } else {
      for (int n = p - 1; n > 1; ) {
        const int q = lpf[n];
        int f = 0;
        do {
          ++f;
          n /= q;
        } while (n % q == 0);
        pess[q].push_back(f);
      }
      if (e >= 2) {
        pess[p].push_back(e - 1);
      }
    }
  }
  for (auto &kv : pess) {
    sort(kv.second.begin(), kv.second.end());
  }
  return pess;
}

int solve(int m) {
if(m<=1000)return brute(m);
  const auto pess = mg(m);
  int ret = 0;
  for (const auto &kv : pess) {
    for (const int e : kv.second) {
      ret += e;
    }
  }
  return ret;
}

int main() {
  iota(lpf, lpf + LIM, 0);
  for (int p = 2; p < LIM; ++p) if (lpf[p] == p) {
    for (int n = 2 * p; n < LIM; n += p) chmin(lpf[n], p);
  }
  
  /*
  for (int m = 1; m <= 100; ++m) {
    const int brt = brute(m);
    const int slv = solve(m);
    const auto pess = mg(m);
    if (brt != slv) {
      cerr << m << ": " << brt << " " << slv << "; ";
      for (const auto &kv : pess) {
        cerr << " " << kv.first << ":";
        for (const int e : kv.second) cerr << e;
      }
      cerr << endl;
    }
  }
  cout << endl;
  //*/
/*
8: 0 2;  2:11
12: 0 2;  2:11
24: 1 3;  2:111
40: 2 4;  2:112
48: 2 4;  2:112
56: 2 4;  2:111 3:1
60: 2 4;  2:112
63: 0 4;  2:11 3:11
65: 1 5;  2:22 3:1
72: 2 4;  2:111 3:1
80: 1 5;  2:122
84: 2 4;  2:111 3:1
88: 2 4;  2:111 5:1
91: 1 5;  2:12 3:11
*/
  
  int N;
  for (; ~scanf("%d", &N); ) {
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
      scanf("%d", &A[i]);
    }
    sort(A.begin(), A.end());
    
    int ans = 0;
    for (int i = 0, j; i < N; i = j) {
      for (j = i; j < N && A[i] == A[j]; ++j) {}
      if ((j - i) % 2 != 0) {
        ans ^= solve(A[i]);
      }
    }
    puts(ans ? "Y" : "X");
  }
  return 0;
}
0