これはしんどい。
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; }
まとめ
コードは短いけど、考察がしんどい。