結果

問題 No.1881 Everything is the same...
ユーザー 👑 hos.lyric
提出日時 2022-03-18 23:19:28
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,372 bytes
コンパイル時間 1,801 ms
コンパイル使用メモリ 134,840 KB
実行使用メモリ 10,656 KB
最終ジャッジ日時 2024-10-03 08:29:48
合計ジャッジ時間 5,599 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 TLE * 1 -- * 41
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0