okura diary

おもに競技プログラミングの日記

ACL1 B. Sum is Multiple

Math ARC

考察

式を整理すると、 $a$ を任意の整数として $2Na = k(k + 1)$ が成り立つような最小の $k$ を求める問題である。
$2N$ の素因数が $k, k + 1$ にどのように振り分けられているのかが気になる。
$2N = pq$ と置き、 $k$ が $p$ の倍数、 $k + 1$ が $q$ の倍数であるとしよう。 $p$ の数はそんなに多くないのでこれを固定して全部試すのは可能。
いまおいた仮定から、整数 $x, y$ を用いて $k = px, k + 1 = qy$ となるが、ここで $k$ を消去すると $px + 1 = qy \Leftrightarrow -px + qy = 1$ となる。
これは馴染みのある形で、extgcdで解ける不定方程式である。これを解いて、 $x > 0$ を満たす $x$ が最小の解を求めれば、 $px$ が求めたかった $k$ である。

拡張ユークリッドと中国剰余定理

この問題の想定解ではCRT(中国剰余定理)を用いている(ACL記念回なので使うのはそれはそう...)。自分もどうせCRT使うんだろうとメタ読みして居たのだが先にextgcdで解ける形になったのでそちらで解いてしまった。自分の中でこの2つの問題は結びついていなかったが、実質的にほぼ同じであることにこの問題で気付かされた。

例えば $px + qy = 1$ は今回の変形の逆で $px = k$ と置くことで $\begin{cases} px = k \\ qy = 1 - k \end{cases}$ となり $\begin{cases} k \equiv 0 \ (mod p) \\ k \equiv 1 \ (mod q) \end{cases}$ を解くのと同じことになる。逆も似たように変形できる。

void solve() {
  ll N;
  cin >> N;
  auto fac = factorize(2 * N);
  int M = fac.size();
  ll ans = LLINF;
  for (int i = 0; i < (1 << M); i++) {
    ll mul = 1ll;
    for (int j = 0; j < M; j++) {
      if ((i >> j) & 1) mul *= fac[j].second;
    }
    ll a, b;
    ll p = mul, q = 2 * N / mul;
    extgcd(p, q, a, b);
    if (a >= 0ll) {
      ll d = ((a / q) + 1);
      a -= d * q;
      b += d * p;
    }
    if (b <= 0ll) {
      ll d = ((-b) / p + 1);
      a -= d * q;
      b += d * p;
    }
    ll d1 = (b - 1) / p;
    ll d2 = (-1 - a) / q;
    ll d = min(d1, d2);
    a -= d * q;
    b += d * p;
    assert(a <= -1);
    assert(b >= 1);
    chmin(ans, p * (-a));
  }
  cout << ans << endl;
  return;
}