[AtCoder] ARC 110 A – Redundant Redundancy

2020年12月6日2020年12月12日

問題

方針

結論からいうと、\( 2 \) から \( N \) までの最小公倍数を \( l \) とすると、\( l + 1 \) となります。以下では、このように考えつかなかった場合を考えます。

\( N! + 1 \) は \( 10^{13} \) を超える可能性があるので不適です。\( 2 \leq j \leq i \) を満たす \( j \) に対して、\( t_i \bmod j \) を満たす \( t_i \) を求めることを考えます。初期値は、\( t_1 = 1 \) です。ここで、\( t_i \) まで求まったとして、\( t_{i + 1} \) を求めます。下記を方程式を満たす最小の \( k \ (1 \leq k \leq i + 1) \) を求めます。

\[t_{i + 1} = t_{i}k \bmod (i + 1) = 0 \]

このとき、\( t_{i + 1} = t_{i}k \) と更新されます。したがって、\( t_{N} + 1 \) が答えとなります。

コード

最小公倍数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// 最大公約数
ll gcd(ll m, ll n) {
  if (n == 0) return m;
  else return gcd(n, m % n);
}

// 最小公倍数
ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

int main() {
    ll N;
    cin >> N;
    ll l = 1;
    for (ll i = 2; i <= N; i++) {
        l = lcm(l, i);
    }
    cout << l + 1 << "\n";
    return 0;
}

この記事の解法

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ll N;
    cin >> N;
    ll k = 1;
    for (int i = 2; i <= N; i++) {
        if (k % i != 0) {
            for (int j = 2; j <= N; j++) {
                if ((k * j) % i == 0) {
                    k *= j;
                    break;
                }
            }
        }
    }
    cout << k + 1 << "\n";
    return 0;
}