🐥

ARC 004 | C - 平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi )

2020/10/28に公開

競プロ

数式変換

gcd

tech

問題

考えたこと

1からNまでの正整数を足すと以下の式となる。

\frac{N(N+1)}{2}

ここから $M$ がなくなって、平均が $X/Y$ と等しくなるので以下となる。

\frac{\frac{N(N+1)}{2}-M}{N} = \frac{X}{Y}

変形すると以下となる。

\frac{N+1}{2}-\frac{M}{N}=\frac{X}{Y}

\frac{N+1}{2}-\frac{X}{Y}=\frac{M}{N} \tag{1}

$N$ と $M$ の条件は $1\leq M \leq N$ なので $N$ で割ると以下となる。

\frac{1}{N} \leq \frac{M}{N} \leq 1

式(1)と $\frac{M}{N}\leq1$ より以下が成り立つ。

\frac{N+1}{2}-\frac{X}{Y}\leq1

N+1-2\frac{X}{Y}\leq2

N\leq 2\frac{X}{Y}+1 \tag{2}

式(1)を変形させると以下となる。

2\left( \frac{M}{N} + \frac{X}{Y} \right) -1 = N

上記と $\frac{1}{N}\leq \frac{M}{N}$ の条件より以下となる。

2\left( \frac{1}{N} + \frac{X}{Y} \right) -1 \leq N

2\frac{X}{Y} + \left(\frac{2}{N}-1\right) \leq N \tag{3}

$1\leq N$ のため $\left(\frac{2}{N}-1 \right)$ は常に-1以上となる。
よって(3)は以下に変形できる。

2\frac{X}{Y} -1 \leq N \tag{4}

よって、式(2)(4)の条件より $N$ は以下を満たす。

2\frac{X}{Y} -1 \leq N \tag{4} \leq 2\frac{X}{Y}+1

これにより $N$ の候補は最大3つに絞られる。各Nに対して式(1)から導かれる以下の $M$ を求めて $M$ と $N$ が $1\leq M \leq N$ の条件みたしていればそれが解である。ここでMは整数なので $N$ は $Y$ で割り切れる必要がある。

M =\frac{N(N+1)}{2}-N\frac{X}{Y}

コード

実装時に気をつけること

$X$ が非常に大きい( $X \leq 10^{18}$ )ので $X$ と $Y$ は約分する
$N$ が $Y$ で割り切れるか確認する

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

ll gcd(ll a, ll b) {
  if (b == 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}

int main() {
  string s;
  cin >> s;
  ll x = 0;
  ll y = 0;
  {
    int pos = s.find('/');
    for (int i = 0; i < pos; i++) {
      x = x * 10 + (s[i] - '0');
    }
    for (int i = pos + 1; i < s.size(); i++) {
      y = y * 10 + (s[i] - '0');
    }
  }
  // 約分する
  ll g = gcd(x, y);
  x /= g;
  y /= g;
  bool found = false;
  ll minN = 2 * x / y - 1;
  ll maxN = 2 * x / y + 1;
  for (ll n = minN; n <= maxN; n++) {
    if (n % y != 0) {
      continue;
    }
    ll m = n * (n + 1) / 2 - n / y * x;
    if (0 < m && m <= n) {
      cout << n << " " << m << endl;
      found = true;
    }
  }

  if (!found) {
    cout << "Impossible" << endl;
  }
}

参考

http://tutuz.hateblo.jp/entry/2018/05/06/21460

問題

考えたこと

コード

参考

Discussion