https://colopl2018-qual.contest.atcoder.jp/tasks/colopl2018_qual_c
解法
https://colopl2018-qual.contest.atcoder.jp/submissions/1844499
「B-A≦35」という制約と「400点」ということから何かしら全探索をするのだろうと推測する。
連続する数に対して互いに素ということを考えると、[A,B]の中で偶数の数は最大1つしか選べないことが分かる。
しかも、35という数は半分全列挙的な雰囲気が出ているので、奇数の数をどう選ぶかを全探索する。
奇数の数を選ぶか選ばないかはビットをつかったループでやるといい。
具体的には「msk := 下位iビット目が1ならばi番目の奇数は選ぶ」というのを回していく。
偶数を選択をする前に、選ばれた奇数だけで全ての組が互いに素であるかを確認しよう。
こうすることで、選んだ偶数を入れても互いに素になるかは、奇数と偶数のチェックだけで済む。
あとは、条件をみたす個数を数え上げる。
ll A, B; //--------------------------------------------------------------------------------------------------- void _main() { cin >> A >> B; vector<ll> v[2]; for (ll x = A; x <= B; x++) v[x % 2].push_back(x); int n = v[1].size(); int m = v[0].size(); int ans = 0; rep(msk, 0, 1 << n) { vector<ll> x; rep(i, 0, n) if (msk & (1 << i)) x.push_back(v[1][i]); int ok = 1; int nm = x.size(); rep(i, 0, nm) rep(j, i + 1, nm) if (gcd(x[i], x[j]) != 1) ok = 0; if (ok) ans++; else continue; rep(mm, 0, m) { int ok = 1; rep(i, 0, nm) if (gcd(x[i], v[0][mm]) != 1) ok = 0; if (ok) ans++; } } cout << ans << endl; }