結果

問題 No.101 ぐるぐる!あみだくじ!
ユーザー takeya_okinotakeya_okino
提出日時 2019-09-07 15:37:41
言語 Java19
(openjdk 21)
結果
WA  
実行時間 -
コード長 969 bytes
コンパイル時間 2,121 ms
コンパイル使用メモリ 73,672 KB
実行使用メモリ 60,592 KB
最終ジャッジ日時 2023-09-09 03:21:13
合計ジャッジ時間 9,616 ms
ジャッジサーバーID
(参考情報)
judge12 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 121 ms
55,924 KB
testcase_01 AC 188 ms
58,280 KB
testcase_02 WA -
testcase_03 TLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
権限があれば一括ダウンロードができます

ソースコード

diff #

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    int[] sig = new int[n];
    for(int i = 0; i < n; i++) {
      sig[i] = i;
    }
    for(int i = 0; i < k; i++) {
      int x = sc.nextInt() - 1;
      int y = sc.nextInt() - 1;
      sig[x] = sig[y];
      sig[y] = sig[x];
    }
    int[] sig2 = new int[n];
    for(int i = 0; i < n; i++) {
      sig2[sig[i]] = i;
    }
    int[] b = new int[n];
    for(int i = 0; i < n; i++) {
      int t = 1;
      int p = sig2[i];
      while(sig2[p] != i) {
        t++;
        p = sig2[p];
      }
      b[i] = t;
    }
    long lcm = 1;
    for(int i = 0; i < n; i++) {
      long g = gcd(lcm, (long)b[i]);
      lcm = g * (lcm / g) * ((long)b[i] / g);
    }
    System.out.println(lcm);
  }

  public static long gcd(long a, long b) {
    if(b == 0) return a;
    return gcd(b, (a % b));
  }
}
0