結果

問題 No.101 ぐるぐる！あみだくじ！
コンテスト
ユーザー kyuna
提出日時 2019-08-18 09:02:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 666 bytes
コンパイル時間 736 ms
コンパイル使用メモリ 71,948 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-01 13:35:28
合計ジャッジ時間 2,067 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <algorithm>
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
inline long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }

int main() {
    int n, k; cin >> n >> k;
    vector<int> nxt(n); iota(nxt.begin(), nxt.end(), 0);
    while (k--) {
        int a, b; cin >> a >> b; a--, b--;
        swap(nxt[a], nxt[b]);
    }
    long long res = 1;
    for (int i = 0; i < n; i++) {
        int cnt = 0;
        for (int x = i; !cnt || x != i; x = nxt[x]) cnt++;
        res = lcm(res, cnt);
    }
    cout << res << endl;
    return 0;
}
0