ferinの競プロ帳

競プロについてのメモ

AGC022 B - GCD Sequence

問題ページ
B - GCD Sequence

考えたこと

  • 全部2の倍数にしたいなーと思う
  • 全体のgcdだけでなく要素の値の上限にも引っかかる
  • とりあえず実験
  • 小さい数でいれられるのをいれていってみると 2,3,10,… とかになる
  • この調子だと上限30000なんてすぐに超えて人生終了
  • 制約がかなり厳しいので何かきれいな構成が存在するはずと思って考える
  • 素数がどうこうとかいろいろ迷走する
  • 2の倍数が3k個存在すればその和は3の倍数になるのでは?みたいな気分になる
  • N = 3k+2 なら (2 4 6 8 10 12 14 16 18)(3 9) みたいにすれば 2の倍数の和が3の倍数、3の倍数の和が2の倍数になる
  • N = 3k+3, 3k+4 のときも3の倍数を適当に加えるとよさそうな気持ちになる
  • ここで2の倍数の個数を確認すると15000個で2の倍数でなく3の倍数の個数は5000個なので20000個でぴったり
  • これならきれいだしよさそうな気持ちになったので投げると落ちる
  • N = 3k+3 のとき3の倍数の和が奇数になっていてだめ
  • 追加する3の倍数を 6k+3 でなく 6の倍数にできればok
  • 6の倍数は2の倍数の方ですでに消費されているので使えない
  • 使う数を (6k+2,6k+4 k>=0)、(3k+3 k>=0)、(6の倍数) に分類していい感じに組み合わせたい
  • 1つ目のグループから使う個数は N=6~8で2個、N=9~11で4個、…みたいになる
  • 2つ目のグループから使う個数は基本的に N-(1つ目のグループから使う個数) になる
  • ただし奇数個使おうとするとだめなのでそのときは-1する
  • 3つ目のグループから使う個数は残り全部
  • 1つ目のグループから取り出すやつも2つ目のグループから取り出すやつも和は6の倍数になるので6の倍数は何個突っ込んでも良い
  • 投げたら通る

乱択通るらしくマジ?って言ってる 冷静に考えると確かに通りそう

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define PB push_back

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n;
  cin >> n;

  if(n == 3) {
    cout << "2 5 63" << endl;
    return 0;
  }
  if(n == 4) {
    cout << "2 5 20 63" << endl;
    return 0;
  }


  int t = min(10000LL, (n - 3) / 3 * 2 + 2);
  int u = min(5000LL, n - t);
  if(u%2) u--;
  int v = n - t - u;

  VI ans;
  int a = 2;
  int d = 0;
  REP(i, t) {
    ans.PB(a);
    d += a;
    a += 2;
    if(a % 6 == 0) a += 2;
  }

  a = 3;
  REP(i, u) {
    ans.PB(a);
    a += 6;
  }

  a = 6;
  REP(i, v) {
    ans.PB(a);
    a += 6;
  }

  REP(i, ans.size()) cout << ans[i] << (i==ans.size()-1?"\n":" ");

  return 0;
}