結果
問題 | No.2979 直角三角形の個数 |
ユーザー |
👑 |
提出日時 | 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 |
ソースコード
#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; }