結果

問題 No.2755 行列の共役類
ユーザー AerenAeren
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif
template<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 BEGIN
template<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 END
template<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 END
int 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*C
0 1 0 1
0<=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=c
d*x + (1-a)*y - b = 0 mod C has a solution
*/
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0