結果

問題 No.2979 直角三角形の個数
コンテスト
ユーザー 👑 ygussany
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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