連絡網 [yukicoder No.826] - はまやんはまやんはまやん

前提知識

解説

BFSをして、到達可能性を判定していくやつをやろう。
　
まず状態はN個でいいとして、問題が遷移数である。
N≦10^6なので、下手にやるとTLEしそうな感じがある。
ある頂点cuからの遷移先は「cuの2以上の約数」と「cuの倍数」である。
これを全て試しても全体の計算量はO(NlogN)のはずなのだが、やるとTLEした。
　
高速化を考えよう。
例えば、ある頂点cuの倍数の遷移として、
cu*2, cu*3, cu*4, cu*5, cu*6
があるとする。
この中で、cu*4はcu*2からも遷移がある。
同様にcu*6もcu*2やcu*3からも遷移がある。
つまり、合成数でかけている遷移先は、素数でかけている遷移先からの遷移でまかなえるということである。
なので、倍数の遷移は素数でかけている遷移しか考える必要がない。
　
約数サイドも同様である。
合成数で割っている遷移先は、素数で割っている遷移先でまかなえる。
よって、約数も素因数で割ったときの遷移だけでいい。
　
これでだいぶ遷移が減らせるので、AC

int N, P;
int vis[1010101];
vector<int> EP[1010101];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> P;

	auto primes = makePrimes(N);
	fore(p, primes) for (int x = p; x <= N; x += p) EP[x].push_back(p);

	int ans = 0;
	queue<int> que;

	vis[P] = 1;
	que.push(P);

	while (!que.empty()) {
		int cu = que.front(); que.pop();
		ans++;

		fore(p, EP[cu]) {
			int to = cu / p;
			if (1 < to and !vis[to]) {
				vis[to] = 1;
				que.push(to);
			}
		}

		fore(p, primes) {
			int to = p * cu;
			if (N < to) break;
			if (!vis[to]) {
				vis[to] = 1;
				que.push(to);
			}
		}
	}

	cout << ans << endl;
}