結果

問題 No.2755 行列の共役類
ユーザー AerenAeren
提出日時 2024-05-10 23:19:52
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 6,986 bytes
コンパイル時間 3,078 ms
コンパイル使用メモリ 257,432 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-20 07:36:56
合計ジャッジ時間 8,866 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 59 WA * 7
権限があれば一括ダウンロードができます

ソースコード

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

*/
0