AtCoder ABC #306 (トヨタ自動車プログラミングコンテスト2023#3) : G - Return to 1

Gまで割と速く解けた。
https://atcoder.jp/contests/abc306/tasks/abc306_g

問題

有向グラフが与えられる。1番の頂点から初めて、辺に沿って移動することを10^10^100回繰り返し、1番の頂点にいる状態を作れるか。

解法

各点vについて以下を求めよう。これはBFSを複数回行えば実行可能。

• v→頂点1→vと戻る最短経路
• vを含む閉路長のGCD

あとは「v→頂点1→vと戻る経路」がある点について、上記2値のGCDを取る。
これが10^10^100の約数ならばよい。

int T,N,M;
vector<int> E[2][202020];
ll dp[2][202020];
ll G[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		FOR(i,N) {
			E[0][i].clear();
			E[1][i].clear();
			dp[0][i]=dp[1][i]=1LL<<30;
			G[i]=0;
		}
		FOR(i,M) {
			cin>>x>>y;
			E[0][x-1].push_back(y-1);
			E[1][y-1].push_back(x-1);
		}
		FOR(j,2) {
			dp[j][0]=0;
			queue<int> Q;
			Q.push(0);
			while(Q.size()) {
				int cur=Q.front();
				Q.pop();
				FORR(e,E[j][cur]) {
					if(dp[j][e]==1LL<<30) {
						dp[j][e]=dp[j][cur]+1;
						Q.push(e);
					}
					else {
						G[e]=__gcd(G[e],dp[j][cur]+1-dp[j][e]);
					}
				}
			}
		}
		ll TG=0;
		for(i=1;i<N;i++) if(dp[0][i]<1LL<<30&&dp[1][i]<1<<30) {
			TG=__gcd(TG,dp[0][i]+dp[1][i]);
			TG=__gcd(TG,G[i]);
		}
		if(TG==0) {
			cout<<"No"<<endl;
		}
		else {
			while(TG%2==0) TG/=2;
			while(TG%5==0) TG/=5;
			if(TG==1) {
				cout<<"Yes"<<endl;
			}
			else {
				cout<<"No"<<endl;
			}
		}
	}
}

まとめ

似た問題どこかで解いてそう。