けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ARC A - Redundant Redundancy (灰色, 300 点)

言語「text (cat)」で AC を取れる数少ない問題の一つ

問題概要

正の整数  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;
}

解法 (2)

別解というほどでもないけど、 N = 30 のときの答えは、 N = 1, 2, \dots, 30 のすべての場合の上位互換なので、その数値を 1 個出力するだけでも OK。

AtCoder 言語別 AC 数ランキングで、text (cat) 部門を目指している方はぜひ!!

2329089562801