kmjp's blog

競技プログラミング参加記です

yukicoder : No.2755 行列の共役類

これはしんどい。
https://yukicoder.me/problems/no/2755

問題

正整数Bと、Bの約数Cが与えられる。
2次正方行列(a b)(c d)において、以下を満たす値に対応する点を持つグラフを考える。

  • aとBは互いに素
  • b % C = 0
  • c % B = 0
  • d % B = 1

2点P,Qは、PR-RQまたはQR-PRの各成分がBの倍数であるとき、辺を持つ。
このグラフの連結成分はいくつか。

解法

a,bがB未満のものだけ考える。
このグラフは、連結成分内は完全グラフになる。
その場合、BFSをすれば1頂点から連結先頂点を列挙できる。
この特性を生かし、未訪問の頂点を1つ見つけるたびに連結先を列挙すれば、連結成分数を求めることができる。

Pに対しRを総当たりし、条件を満たすQをたどろう。

int B,C;
int found[606*606];
int rev[606];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>B>>C;
	int ret=0;
	
	FOR(x,B) FOR(y,B) if(x*y%B==1) rev[x]=y;
	
	FOR(i,B*B) {
		if(__gcd(i/B,B)>1) continue;
		if(i%B%C) continue;
		if(found[i]) continue;
		ret++;
		if(ret>100) {
			cout<<"100+"<<endl;
			return;
		}
		FOR(j,B*B) {
			if(__gcd(j/B,B)>1) continue;
			if(j%B%C) continue;
			int a=i/B;
			int b=(i/B*(j%B)+(i%B)+B-(j%B))*rev[j/B]%B;
			found[a*B+b]=1;
		}
	}
	cout<<ret<<endl;
	
}

まとめ

コードは短いけど、考察がしんどい。