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までの正整数を足すと以下の式となる。

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

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

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

変形すると以下となる。

N+12MN=XY\frac{N+1}{2}-\frac{M}{N}=\frac{X}{Y}
N+12XY=MN(1)\frac{N+1}{2}-\frac{X}{Y}=\frac{M}{N} \tag{1}

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

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

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

N+12XY1\frac{N+1}{2}-\frac{X}{Y}\leq1
N+12XY2N+1-2\frac{X}{Y}\leq2
N2XY+1(2)N\leq 2\frac{X}{Y}+1 \tag{2}

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

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

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

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

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

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

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

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

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

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

コード

実装時に気をつけること

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

参考