問題概要

正の整数 $N$ が与えられる。

$1, 2, \dots, N$ のどれで割っても 1 あまる整数 ( $1$ 以上 $10^{13}$ 以下) を一つ求めよ。

制約

$1 \le N \le 30$

解法 (1)

$1, 2, \dots, N$ の最大公倍数を $L$ として、 $L+1$ が答えになる。似た発想をする問題として、次のやつがあった。

drken1215.hatenablog.com

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

long long GCD(long long a, long long b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}

long long LCM(long long a, long long b) {
    long long g = GCD(a, b);
    return a / g * b;
}

int main() {
    long long N;
    cin >> N;
    long long res = 1;
    for (int n = 1; n <= N; ++n) res = LCM(res, n);
    cout << res + 1 << endl;
}