新艦掘り終わったし昼寝もした私に死角はありません！いや、ないかもしれません！

結果

A,B,C,DはAC。Eは後日自力AC。

C - Anti-Division

一つ一つ割り切れるかどうか判定していると時間足りません( $O(B-A)$ )。割り切れるやつを考えて引けばいいです。
注意点としてはC,D両方で割り切れるやつ(公倍数)があること。二重カウントになるので調整しましょう。

A,B間-(Cで割り切れるの+Dで割り切れるの-C,Dの最小公倍数で割り切れるの)

締め切り順に並び替える*1だけです。

まず最短距離が 2 であるような頂点対が最大何個できるか考えますと、スター型にすりゃいいので $\sum_{i=1}^{N-1} i=\frac{1}{2}(N-1)(N-2)$ 個。

ここから葉と葉にパスを通すと最短経路が1になるためペアが一つ減ります。

スター型を作り、Kとの差だけ葉と葉にパスを通すとすればよいです。

単純…ループがない…さらに連結。つまり木構造か！*2
と誤解したため最大値からKまでもっていく方法がわからず時間切れ。アルゴリズムがどうとか以前に基本的な定義からですねぇ…。

とりあえず基礎からちゃんとやらないとだめですね。

*1:いつもやってることだな！

*2:閉路とループを混同している