The Beatles [Codeforces Round #549 (Div. 1) A]

https://codeforces.com/contest/1142/problem/A

円状に頂点1から頂点nkまで並んでいる。
1, K+1, 2K+1, ...のようにN個のお店がある。
　
最初に頂点sと距離lを決める。
s, s+l, s+2l, ... のように距離lで頂点の数が増える方向に移動して、sに戻ってきたら操作を終える。
頂点sから最も近いお店との距離をa, 頂点s+lから最も近いお店との距離をbとする。
この時、s,lを適切に決めた時、操作中に訪れる頂点の最小数と最大数を求めよ。
　
1≦nk≦10^5
0≦a,b≦k/2

解説

https://codeforces.com/contest/1142/submission/52045701

まず、操作中に訪れる頂点の数は、nk/gcd(nk,l)となる。
よって、lがわかれば、頂点の数が分かることになる。
　
とりあえず、全探索方針でまずは考える。
頂点sは頂点が円状であり、個々のお店で特に違いは無いので、
あるお店から距離aだけ離れた頂点の2択を試せばいい。
次に距離lであるが、距離lでなく2番目に訪れる頂点tを全探索することにしよう。
これは、お店から距離bだけ離れた頂点だが、2N個しかないので、こちらも全探索できる。
なので、頂点sと頂点t（l=t-s）を全探索できるので、それぞれについて訪れる頂点を求めて、
最小と最大を取ると答え。

ll N, K, A, B;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> K >> A >> B;

	ll ans_mi = infl;
	ll ans_ma = -1;

	rep(d, -1, 2) if (d != 0) {
		ll s = A * d + 1;
		if (s <= 0) s += K;

		rep(n, 0, N) rep(dd, -1, 2) if (dd != 0) {
			ll t = B * dd + 1 + K * n;
			ll l = t - s;

			if (l <= 0) l += N * K;
			if (N*K < l) l -= N * K;

			ll ans = N * K / gcd(N * K, l);

			chmin(ans_mi, ans);
			chmax(ans_ma, ans);
		}
	}

	printf("%lld %lld\n", ans_mi, ans_ma);
}