🍣

ARC 110 | A - Redundant Redundancy

2020/12/06に公開

競プロ

tech

問題

考えたこと

2で割って1余る数というのは2の倍数に1を足した数、たとえば3などである。
3, 4, ... の以降も同じで指定の数の倍数に1を足した数である。

よって単純に考えると $2$ から $N$ までかけ合わせ、1を足せば答えとなる。
しかし、 $N$ は30以下なので、すべてかけあわせると条件の $10^{13}$ を超えてしまう。

$2$ から $N$ までのすべての倍数をもとめるには最小公倍数を求めればいい。
$N = 30$ のときの最小公倍数が $10^{13}$ 以下なのでこの方法が正解である。

コード

実装時のTips

gcdを使ってlcmを求める

#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;

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

ull lcm(ull a, ull b) {
  return a * b / gcd(a, b);
}

int main() {
  ll n;
  cin >> n;
  ll ans = 1;
  for (int i = 2; i <= n; i++) {
    ans = lcm(ans, i);
  }
  cout << ans + 1 << endl;
}

コンテスト中は何をかんがえていたか

コンテスト中にWAを一回だしていてその時は $2$ から $N$ を全部掛け合わせてやってました。
WAだったので $N$ が最大の30のときのテストケースを作成してやってみるとオーバーフローしていたので気づきました。
まあ普通に30までかけ合わせれば0の数がどう考えても13個より大きくなるのでちょっと考えればわかることでした。

その後に因数を求めて各数値の因数の最大数をかけあわせればいいことに気づいてACしました。以下がそのコードです。
やっていることは実際はLCMだったので解説のとおりにかけばすっきりします。

#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;

vector<pair<ll, ll>> primeFactorize(ll n) {
  vector<pair<ll, ll>> r;
  for (ll i = 2; i * i <= n; i++) {
    if (n % i != 0) {
      continue;
    }
    int ex = 0;
    while (n % i == 0) {
      ex++;
      n /= i;
    }
    r.push_back({i, ex});
  }
  if (n > 1) {
    r.push_back({n, 1});
  }
  return r;
}

int main() {
  ll n;
  cin >> n;
  ll ans = 1;
  vector<ll> fc(31);
  for (int i = n; i >= 2; i--) {
    auto r = primeFactorize(i);
    for (auto [k, v] : r) {
      fc[k] = max(fc[k], v);
    }
  }
  for (int i = 2; i < fc.size(); i++) {
    ans *= pow(i, fc[i]);
  }
  cout << ans + 1 << endl;
}

ARC 110 | A - Redundant Redundancy

問題

考えたこと

コード

コンテスト中は何をかんがえていたか

参考

Discussion