結果
問題 | No.2755 行列の共役類 |
ユーザー |
|
提出日時 | 2024-05-10 23:19:43 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,465 ms / 3,500 ms |
コード長 | 6,985 bytes |
コンパイル時間 | 3,778 ms |
コンパイル使用メモリ | 255,744 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-12-20 07:36:47 |
合計ジャッジ時間 | 8,913 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 66 |
ソースコード
// #pragma GCC optimize("O3,unroll-loops")#include <bits/stdc++.h>// #include <x86intrin.h>using namespace std;#if __cplusplus >= 202002Lusing namespace numbers;#endiftemplate<bool Enable_small_to_large = true>struct disjoint_set{int n, _group_count;vector<int> p;vector<list<int>> group;disjoint_set(){ }disjoint_set(int n): n(n), _group_count(n), p(n, -1), group(n){ assert(n >= 0);for(auto i = 0; i < n; ++ i) group[i] = {i};}int make_set(){p.push_back(-1);group.push_back(list<int>{n});++ _group_count;return n ++;}int root(int u){return p[u] < 0 ? u : p[u] = root(p[u]);}bool share(int a, int b){return root(a) == root(b);}int size(int u){return -p[root(u)];}bool merge(int u, int v){u = root(u), v = root(v);if(u == v) return false;-- _group_count;if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v);p[u] += p[v], p[v] = u;group[u].splice(group[u].end(), group[v]);return true;}bool merge(int u, int v, auto act){u = root(u), v = root(v);if(u == v) return false;-- _group_count;bool swapped = false;if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v), swapped = true;act(u, v, swapped);p[u] += p[v], p[v] = u;group[u].splice(group[u].end(), group[v]);return true;}int group_count() const{return _group_count;}const list<int> &group_of(int u){return group[root(u)];}vector<vector<int>> group_up(){vector<vector<int>> g(n);for(auto i = 0; i < n; ++ i) g[root(i)].push_back(i);g.erase(remove_if(g.begin(), g.end(), [&](auto &s){ return s.empty(); }), g.end());return g;}void clear(){_group_count = n;fill(p.begin(), p.end(), -1);for(auto i = 0; i < n; ++ i) group[i] = {i};}friend ostream &operator<<(ostream &out, disjoint_set dsu){auto gs = dsu.group_up();out << "{";if(!gs.empty()) for(auto i = 0; i < (int)gs.size(); ++ i){out << "{";for(auto j = 0; j < (int)gs[i].size(); ++ j){out << gs[i][j];if(j + 1 < (int)gs[i].size()) out << ", ";}out << "}";if(i + 1 < (int)gs.size()) out << ", ";}return out << "}";}};// DEBUG BEGIN#ifdef LOCAL// DECLARATION BEGINtemplate<class L, class R> ostream &operator<<(ostream &out, const pair<L, R> &p);template<class Tuple, size_t N> struct _tuple_printer;template<class... Args> ostream &_print_tuple(ostream &out, const tuple<Args...> &t);template<class ...Args> ostream &operator<<(ostream &out, const tuple<Args...> &t);template<class T> ostream &operator<<(typename enable_if<!is_same<T, string>::value, ostream>::type &out, const T &arr);ostream &operator<<(ostream &out, const _Bit_reference &bit);template<size_t SZ> ostream &operator<<(ostream &out, const bitset<SZ> &b);template<class T, class A, class C>ostream &operator<<(ostream &out, priority_queue<T, A, C> pq);// DECLARATION ENDtemplate<class L, class R> ostream &operator<<(ostream &out, const pair<L, R> &p){return out << "{" << p.first << ", " << p.second << "}";}template<class Tuple, size_t N> struct _tuple_printer{static ostream &_print(ostream &out, const Tuple &t){ return _tuple_printer<Tuple, N-1>::_print(out, t) << ", " << get<N-1>(t); }};template<class Tuple> struct _tuple_printer<Tuple, 1>{static ostream &_print(ostream &out, const Tuple& t){ return out << get<0>(t); }};template<class... Args> ostream &_print_tuple(ostream &out, const tuple<Args...> &t){return _tuple_printer<decltype(t), sizeof...(Args)>::_print(out << "{", t) << "}";}template<class ...Args> ostream &operator<<(ostream &out, const tuple<Args...> &t){return _print_tuple(out, t);}template<class T> ostream &operator<<(typename enable_if<!is_same<T, string>::value, ostream>::type &out, const T &arr){if(arr.empty()) return out << "{}";out << "{";for(auto it = arr.begin(); it != arr.end(); ++ it){out << *it;next(it) != arr.end() ? out << ", " : out << "}";}return out;}ostream &operator<<(ostream &out, const _Bit_reference &bit){return out << bool(bit);}template<size_t SZ> ostream &operator<<(ostream &out, const bitset<SZ> &b){for(auto i = 0; i < SZ; ++ i) out << b[i];return out;}template<class T, class A, class C>ostream &operator<<(ostream &out, priority_queue<T, A, C> pq){vector<T> a;while(!pq.empty()) a.push_back(pq.top()), pq.pop();return out << a;}template<class Head>void debug_out(Head H){ cerr << H << endl; }template<class Head, class... Tail>void debug_out(Head H, Tail... T){ cerr << H << ", ", debug_out(T...); }void debug2_out(){ }template<class Head, class... Tail>void debug2_out(Head H, Tail... T){ cerr << "\n"; for(auto x: H) cerr << x << ",\n"; debug2_out(T...); }template<class Width, class Head>void debugbin_out(Width w, Head H){for(auto rep = w; rep; -- rep, H >>= 1) cerr << (H & 1);cerr << endl;}template<class Width, class Head, class... Tail>void debugbin_out(Width w, Head H, Tail... T){for(auto rep = w; rep; -- rep, H >>= 1) cerr << (H & 1);cerr << ", "; debugbin_out(w, T...);}enum CODE{ CCRED = 31, CCGREEN = 32, CCYELLOW = 33, CCBLUE = 34, CCDEFAULT = 39 };#define debug_endl() cerr << endl#define debug(...) cerr << "\033[" << (int)CODE(CCRED) << "mL" << setw(3) << std::left << __LINE__ << std::right << " [" << #__VA_ARGS__ << "] \033["<< (int)CODE(CCBLUE) << "m", debug_out(__VA_ARGS__), cerr << "\33[" << (int)CODE(CCDEFAULT) << "m"#define debug2(...) cerr << "\033[" << (int)CODE(CCRED) << "mL" << setw(3) << std::left << __LINE__ << std::right << " [" << #__VA_ARGS__ << "]\033[" << (int)CODE(CCBLUE) << "m", debug2_out(__VA_ARGS__), cerr << "\33[" << (int)CODE(CCDEFAULT) << "m"#define debugbin(...) cerr << "\033[" << (int)CODE(CCRED) << "mL" << setw(3) << std::left << __LINE__ << std::right << " [" << #__VA_ARGS__ << "]\033[" << (int)CODE(CCBLUE) << "m", debugbin_out(__VA_ARGS__), cerr << "\33[" << (int)CODE(CCDEFAULT) << "m"#else#define debug_endl() 42#define debug(...) 42#define debug2(...) 42#define debugbin(...) 42#endif// DEBUG ENDint main(){cin.tie(0)->sync_with_stdio(0);cin.exceptions(ios::badbit | ios::failbit);int B, C;cin >> B >> C, C = B / C;vector<vector<int>> g(C + 1, vector<int>(C + 1));for(auto x = 0; x <= C; ++ x){for(auto y = 0; y <= C; ++ y){g[x][y] = gcd(x, y);}}int res = 0;disjoint_set dsu(C);for(auto a = 1; a <= B; ++ a){if(gcd(a, B) != 1){continue;}dsu.clear();for(auto b = 0; b < C; ++ b){for(auto d = b + 1; d < C; ++ d){if(d % g[(a - 1) % C][g[b][C]] == 0 && b % g[d][g[(a - 1) % C][C]] == 0){dsu.merge(b, d);}}}debug(a);debug2(dsu.group_up());res += dsu.group_count();}if(res > 100){cout << "100+\n";}else{cout << res << "\n";}return 0;}/*a b*C c d*C0 1 0 10<=a<B, 0<=b<B/C(a,b)*(c*d) = (a*c, a*d+b) = (1, 0)c=invB(a)d=-b*invC(a)(a*x, a*y+b) = (c*x, d*x+y)for some x, y (gcd(x, B) = 1)a=cd*x + (1-a)*y - b = 0 mod C has a solution*/