🍣

ARC 110 | A - Redundant Redundancy

2 min read

問題

https://atcoder.jp/contests/arc110/tasks/arc110_a

考えたこと

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

参考

https://atcoder.jp/contests/arc110/tasks/arc110_a/editorial

Discussion

ログインするとコメントできます