結果

問題 No.2979 直角三角形の個数
ユーザー 👑 ygussanyygussany
提出日時 2024-12-03 01:05:29
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 1,894 ms / 4,000 ms
コード長 1,703 bytes
コンパイル時間 916 ms
コンパイル使用メモリ 31,364 KB
実行使用メモリ 28,536 KB
最終ジャッジ日時 2024-12-03 01:05:42
合計ジャッジ時間 12,152 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,816 KB
testcase_01 AC 3 ms
7,616 KB
testcase_02 AC 3 ms
6,904 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 3 ms
6,916 KB
testcase_07 AC 3 ms
7,464 KB
testcase_08 AC 2 ms
6,912 KB
testcase_09 AC 2 ms
6,828 KB
testcase_10 AC 3 ms
6,820 KB
testcase_11 AC 3 ms
6,840 KB
testcase_12 AC 5 ms
6,944 KB
testcase_13 AC 4 ms
6,816 KB
testcase_14 AC 37 ms
6,820 KB
testcase_15 AC 37 ms
6,856 KB
testcase_16 AC 213 ms
8,048 KB
testcase_17 AC 731 ms
7,532 KB
testcase_18 AC 939 ms
9,324 KB
testcase_19 AC 971 ms
8,860 KB
testcase_20 AC 974 ms
10,644 KB
testcase_21 AC 958 ms
12,408 KB
testcase_22 AC 1,643 ms
25,768 KB
testcase_23 AC 1,654 ms
25,928 KB
testcase_24 AC 3 ms
7,412 KB
testcase_25 AC 3 ms
6,820 KB
testcase_26 AC 3 ms
7,388 KB
testcase_27 AC 12 ms
6,820 KB
testcase_28 AC 1,894 ms
28,536 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

const int bit[8] = {1, 2, 4, 8, 16, 32, 64, 128};

int main()
{
	long long N;
	scanf("%lld", &N);
	
	char comp[800000] = {};
	int i, j, n, div[800000][8], n_div[800000] = {};
	for (n = 1; (long long)(n + 1) * (n + 2) * 2 <= N; n++);
	for (i = 2; i <= n; i++) {
		if (comp[i] != 0) continue;
		for (j = i; j <= n; j += i) {
			comp[j] = 1;
			div[j][n_div[j]++] = i;
		}
		comp[i] = 0;
	}
	
	int k, l, m, max, flag[100001] = {}, prod[128], coeff[128];
	long long ans = 0, tmp;
	for (i = 1, l = 1, coeff[0] = 1; i < bit[7]; i++, l++) {
		for (j = 0; (i & bit[j]) == 0; j++) l--;
		if (l % 2 == 0) coeff[i] = 1;
		else coeff[i] = -1;
	}
	for (k = 2; k <= 20000 && k <= n; k++) {
		for (i = 0; i < n_div[k]; i++) for (j = div[k][i]; j < k; j += div[k][i]) flag[j] = 1;
		for (j = 1 + k % 2, tmp = k * (k + j) * 2; j < k && tmp <= N; j += 2, tmp += k * 4) {
			if (flag[j] != 0) continue;
			ans += N / tmp;
		}
		for (i = 0; i < n_div[k]; i++) for (j = div[k][i]; j < k; j += div[k][i]) flag[j] = 0;
	}
	for (; k <= n; k++) {
		for (i = 0; i < bit[n_div[k]]; i++) for (j = 0, prod[i] = 1; j < n_div[k]; j++) if ((i & bit[j]) != 0) prod[i] *= div[k][j];
		if (k % 2 == 0) {
			for (m = 1; 1; m++) {
				max = N / 2 / k / m - k;
				if (max >= k) max = k - 1;
				if (max < 1) break;
				
				for (i = 0, tmp = 0; i < bit[n_div[k]]; i++) tmp += max / prod[i] * coeff[i];
				ans += tmp;
			}
		} else {
			for (m = 1; 1; m++) {
				max = (N / 2 / k / m - k) / 2;
				if (max > k / 2) max = k / 2;
				if (max < 1) break;
				
				for (i = 0, tmp = 0; i < bit[n_div[k]]; i++) tmp += max / prod[i] * coeff[i];
				ans += tmp;
			}
		}
	}
	printf("%lld\n", ans);
	fflush(stdout);
	return 0;
}
0