結果
問題 | No.1262 グラフを作ろう! |
ユーザー | 👑 ygussany |
提出日時 | 2020-10-16 22:57:41 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 1,780 ms / 3,000 ms |
コード長 | 1,574 bytes |
コンパイル時間 | 566 ms |
コンパイル使用メモリ | 30,836 KB |
実行使用メモリ | 13,652 KB |
最終ジャッジ日時 | 2023-09-28 04:54:25 |
合計ジャッジ時間 | 55,514 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 723 ms
9,564 KB |
testcase_01 | AC | 519 ms
9,744 KB |
testcase_02 | AC | 910 ms
11,024 KB |
testcase_03 | AC | 402 ms
8,092 KB |
testcase_04 | AC | 102 ms
12,640 KB |
testcase_05 | AC | 528 ms
10,324 KB |
testcase_06 | AC | 60 ms
13,192 KB |
testcase_07 | AC | 100 ms
7,060 KB |
testcase_08 | AC | 758 ms
12,944 KB |
testcase_09 | AC | 229 ms
8,712 KB |
testcase_10 | AC | 399 ms
8,968 KB |
testcase_11 | AC | 793 ms
12,928 KB |
testcase_12 | AC | 642 ms
9,476 KB |
testcase_13 | AC | 461 ms
8,604 KB |
testcase_14 | AC | 405 ms
9,096 KB |
testcase_15 | AC | 143 ms
7,548 KB |
testcase_16 | AC | 772 ms
11,948 KB |
testcase_17 | AC | 670 ms
10,908 KB |
testcase_18 | AC | 1,007 ms
11,964 KB |
testcase_19 | AC | 153 ms
11,660 KB |
testcase_20 | AC | 448 ms
13,352 KB |
testcase_21 | AC | 966 ms
10,900 KB |
testcase_22 | AC | 53 ms
11,120 KB |
testcase_23 | AC | 332 ms
8,504 KB |
testcase_24 | AC | 799 ms
11,988 KB |
testcase_25 | AC | 107 ms
9,292 KB |
testcase_26 | AC | 220 ms
10,420 KB |
testcase_27 | AC | 513 ms
12,200 KB |
testcase_28 | AC | 429 ms
11,740 KB |
testcase_29 | AC | 292 ms
12,136 KB |
testcase_30 | AC | 351 ms
10,816 KB |
testcase_31 | AC | 777 ms
10,064 KB |
testcase_32 | AC | 576 ms
10,480 KB |
testcase_33 | AC | 128 ms
7,336 KB |
testcase_34 | AC | 650 ms
13,140 KB |
testcase_35 | AC | 528 ms
8,840 KB |
testcase_36 | AC | 105 ms
6,624 KB |
testcase_37 | AC | 1,052 ms
12,380 KB |
testcase_38 | AC | 620 ms
11,740 KB |
testcase_39 | AC | 283 ms
7,136 KB |
testcase_40 | AC | 399 ms
8,776 KB |
testcase_41 | AC | 364 ms
12,236 KB |
testcase_42 | AC | 942 ms
12,520 KB |
testcase_43 | AC | 484 ms
10,328 KB |
testcase_44 | AC | 529 ms
10,044 KB |
testcase_45 | AC | 905 ms
12,824 KB |
testcase_46 | AC | 273 ms
13,304 KB |
testcase_47 | AC | 168 ms
6,468 KB |
testcase_48 | AC | 803 ms
12,956 KB |
testcase_49 | AC | 1,021 ms
11,592 KB |
testcase_50 | AC | 924 ms
12,016 KB |
testcase_51 | AC | 228 ms
9,004 KB |
testcase_52 | AC | 364 ms
12,884 KB |
testcase_53 | AC | 165 ms
8,532 KB |
testcase_54 | AC | 566 ms
9,520 KB |
testcase_55 | AC | 563 ms
10,248 KB |
testcase_56 | AC | 378 ms
12,840 KB |
testcase_57 | AC | 1,199 ms
12,848 KB |
testcase_58 | AC | 455 ms
8,568 KB |
testcase_59 | AC | 363 ms
12,212 KB |
testcase_60 | AC | 1,094 ms
12,244 KB |
testcase_61 | AC | 356 ms
8,812 KB |
testcase_62 | AC | 874 ms
11,272 KB |
testcase_63 | AC | 477 ms
9,024 KB |
testcase_64 | AC | 521 ms
9,480 KB |
testcase_65 | AC | 188 ms
9,660 KB |
testcase_66 | AC | 399 ms
9,456 KB |
testcase_67 | AC | 337 ms
9,932 KB |
testcase_68 | AC | 239 ms
13,496 KB |
testcase_69 | AC | 356 ms
10,912 KB |
testcase_70 | AC | 765 ms
13,060 KB |
testcase_71 | AC | 409 ms
11,408 KB |
testcase_72 | AC | 808 ms
12,876 KB |
testcase_73 | AC | 519 ms
11,764 KB |
testcase_74 | AC | 130 ms
10,200 KB |
testcase_75 | AC | 467 ms
12,796 KB |
testcase_76 | AC | 362 ms
10,976 KB |
testcase_77 | AC | 294 ms
11,372 KB |
testcase_78 | AC | 533 ms
11,724 KB |
testcase_79 | AC | 889 ms
12,996 KB |
testcase_80 | AC | 756 ms
13,168 KB |
testcase_81 | AC | 226 ms
11,232 KB |
testcase_82 | AC | 349 ms
11,560 KB |
testcase_83 | AC | 698 ms
12,880 KB |
testcase_84 | AC | 391 ms
11,852 KB |
testcase_85 | AC | 903 ms
12,876 KB |
testcase_86 | AC | 452 ms
11,688 KB |
testcase_87 | AC | 730 ms
12,148 KB |
testcase_88 | AC | 214 ms
11,096 KB |
testcase_89 | AC | 641 ms
12,348 KB |
testcase_90 | AC | 117 ms
13,456 KB |
testcase_91 | AC | 118 ms
13,604 KB |
testcase_92 | AC | 119 ms
13,556 KB |
testcase_93 | AC | 125 ms
13,652 KB |
testcase_94 | AC | 119 ms
13,648 KB |
testcase_95 | AC | 1,780 ms
13,440 KB |
ソースコード
#include <stdio.h> int factorize(int n, int p[], int m[]) { int i, k; for (i = 2, k = 0; i * i <= n; i++) { if (n % i != 0) continue; p[k] = i; for (m[k] = 0; n % p[k] == 0; m[k]++, n /= p[k]); k++; } if (n > 1) { p[k] = n; m[k++] = 1; } return k; } int main() { int i, N, M, A; scanf("%d %d", &N, &M); int h, j, k, l[101], ll[101], m[101], p[101], tmp, tmpp, count[1000001] = {}; long long ans = 0, memo[1000001]; for (i = 1; i <= N; i++) memo[i] = -1; for (i = 1; i <= M; i++) { scanf("%d", &A); if (memo[A] != -1) { ans += memo[A]; continue; } else memo[A] = 0; k = factorize(A, p, m); for (j = 0, tmp = A; j < k; j++) l[j] = m[j]; while (tmp > 1) { count[tmp] = A / tmp; for (j = 0, tmpp = tmp; j < k; j++) ll[j] = l[j]; while (tmpp < A) { for (h = 0; h < k && ll[h] == m[h]; h++); if (h == k) break; for (ll[h]++, tmpp *= p[h--]; h >= 0; ll[h] = l[h], h--) { for (j = l[h]; j < m[h]; j++) tmpp /= p[h]; } count[tmp] -= count[tmpp]; } memo[A] += (long long)(tmp - 1) * count[tmp]; for (h = 0; h < k && l[h] == 0; h++); for (l[h]--, tmp /= p[h--]; h >= 0; l[h] = m[h], h--) { for (j = 0; j < m[h]; j++) tmp *= p[h]; } } ans += memo[A]; for (j = 1, l[0] = 1, tmp = p[0]; j < k; j++) l[j] = 0; while (1) { count[tmp] = 0; for (h = 0; h < k && l[h] == m[h]; h++); if (h == k) break; for (l[h]++, tmp *= p[h--]; h >= 0; l[h--] = 0) { for (j = 0; j < m[h]; j++) tmp /= p[h]; } } } printf("%lld\n", ans); fflush(stdout); return 0; }