#567993 (C) No.1262 グラフを作ろう！

提出ソース

結果

問題	No.1262 グラフを作ろう！
ユーザー	ygussany
提出日時	2020-10-16 22:57:41
言語	C (gcc 12.3.0)
結果	AC
実行時間	1,783 ms / 3,000 ms
コード長	1,574 bytes
コンパイル時間	635 ms
コンパイル使用メモリ	32,448 KB
実行使用メモリ	13,568 KB
最終ジャッジ日時	2024-07-20 23:27:49
合計ジャッジ時間	54,726 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	739 ms 9,216 KB
testcase_01	AC	527 ms 8,576 KB
testcase_02	AC	926 ms 10,752 KB
testcase_03	AC	408 ms 7,424 KB
testcase_04	AC	104 ms 12,032 KB
testcase_05	AC	537 ms 9,984 KB
testcase_06	AC	61 ms 13,056 KB
testcase_07	AC	101 ms 6,912 KB
testcase_08	AC	760 ms 12,288 KB
testcase_09	AC	227 ms 6,784 KB
testcase_10	AC	404 ms 8,320 KB
testcase_11	AC	800 ms 12,800 KB
testcase_12	AC	643 ms 8,832 KB
testcase_13	AC	461 ms 7,680 KB
testcase_14	AC	400 ms 8,832 KB
testcase_15	AC	144 ms 6,272 KB
testcase_16	AC	785 ms 11,776 KB
testcase_17	AC	675 ms 10,368 KB
testcase_18	AC	1,016 ms 11,648 KB
testcase_19	AC	153 ms 11,264 KB
testcase_20	AC	457 ms 13,440 KB
testcase_21	AC	958 ms 10,752 KB
testcase_22	AC	55 ms 10,880 KB
testcase_23	AC	335 ms 7,424 KB
testcase_24	AC	798 ms 12,032 KB
testcase_25	AC	109 ms 8,960 KB
testcase_26	AC	225 ms 9,344 KB
testcase_27	AC	517 ms 11,904 KB
testcase_28	AC	436 ms 10,752 KB
testcase_29	AC	297 ms 11,648 KB
testcase_30	AC	349 ms 9,344 KB
testcase_31	AC	777 ms 9,344 KB
testcase_32	AC	572 ms 9,472 KB
testcase_33	AC	131 ms 6,400 KB
testcase_34	AC	653 ms 13,184 KB
testcase_35	AC	516 ms 8,064 KB
testcase_36	AC	105 ms 6,272 KB
testcase_37	AC	1,061 ms 11,516 KB
testcase_38	AC	620 ms 11,008 KB
testcase_39	AC	282 ms 7,040 KB
testcase_40	AC	402 ms 8,192 KB
testcase_41	AC	371 ms 12,160 KB
testcase_42	AC	959 ms 12,032 KB
testcase_43	AC	491 ms 10,368 KB
testcase_44	AC	539 ms 9,728 KB
testcase_45	AC	921 ms 12,564 KB
testcase_46	AC	275 ms 13,416 KB
testcase_47	AC	168 ms 6,400 KB
testcase_48	AC	816 ms 11,520 KB
testcase_49	AC	1,017 ms 11,392 KB
testcase_50	AC	923 ms 12,160 KB
testcase_51	AC	229 ms 7,296 KB
testcase_52	AC	355 ms 12,868 KB
testcase_53	AC	167 ms 7,808 KB
testcase_54	AC	579 ms 8,704 KB
testcase_55	AC	568 ms 9,216 KB
testcase_56	AC	388 ms 11,904 KB
testcase_57	AC	1,194 ms 12,800 KB
testcase_58	AC	458 ms 8,320 KB
testcase_59	AC	367 ms 12,288 KB
testcase_60	AC	1,107 ms 12,288 KB
testcase_61	AC	360 ms 8,448 KB
testcase_62	AC	885 ms 10,624 KB
testcase_63	AC	477 ms 8,192 KB
testcase_64	AC	523 ms 9,088 KB
testcase_65	AC	189 ms 9,472 KB
testcase_66	AC	399 ms 8,832 KB
testcase_67	AC	339 ms 9,984 KB
testcase_68	AC	232 ms 13,220 KB
testcase_69	AC	359 ms 9,600 KB
testcase_70	AC	776 ms 13,056 KB
testcase_71	AC	412 ms 10,880 KB
testcase_72	AC	824 ms 12,756 KB
testcase_73	AC	524 ms 11,136 KB
testcase_74	AC	131 ms 9,600 KB
testcase_75	AC	469 ms 11,136 KB
testcase_76	AC	370 ms 10,880 KB
testcase_77	AC	287 ms 10,368 KB
testcase_78	AC	534 ms 11,392 KB
testcase_79	AC	902 ms 12,928 KB
testcase_80	AC	768 ms 13,112 KB
testcase_81	AC	225 ms 10,240 KB
testcase_82	AC	353 ms 10,624 KB
testcase_83	AC	709 ms 12,800 KB
testcase_84	AC	392 ms 10,752 KB
testcase_85	AC	902 ms 12,736 KB
testcase_86	AC	433 ms 11,008 KB
testcase_87	AC	747 ms 11,904 KB
testcase_88	AC	215 ms 9,984 KB
testcase_89	AC	656 ms 12,380 KB
testcase_90	AC	116 ms 13,568 KB
testcase_91	AC	117 ms 13,440 KB
testcase_92	AC	116 ms 13,440 KB
testcase_93	AC	122 ms 13,568 KB
testcase_94	AC	119 ms 13,568 KB
testcase_95	AC	1,783 ms 13,440 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード