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

公開:2020/10/28
更新:2020/10/28
2 min読了の目安(約2200字TECH技術記事

問題

https://atcoder.jp/contests/arc004/tasks/arc004_3

考えたこと

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}

NMの条件は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を求めてMN1\leq M \leq Nの条件みたしていればそれが解である。ここでMは整数なのでNYで割り切れる必要がある。

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

コード

実装時に気をつけること

  • Xが非常に大きい(X \leq 10^{18})のでXYは約分する
  • NYで割り切れるか確認する
#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;
  }
}

参考