結果
問題 | No.1514 Squared Matching |
ユーザー | Suu0313 |
提出日時 | 2021-06-17 06:20:20 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 566 ms / 4,000 ms |
コード長 | 606 bytes |
コンパイル時間 | 2,232 ms |
コンパイル使用メモリ | 202,916 KB |
実行使用メモリ | 198,584 KB |
最終ジャッジ日時 | 2023-08-30 15:08:33 |
合計ジャッジ時間 | 12,778 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 566 ms
198,584 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,376 KB |
testcase_06 | AC | 8 ms
6,236 KB |
testcase_07 | AC | 93 ms
40,316 KB |
testcase_08 | AC | 502 ms
191,236 KB |
testcase_09 | AC | 425 ms
167,392 KB |
testcase_10 | AC | 465 ms
181,384 KB |
testcase_11 | AC | 488 ms
188,596 KB |
testcase_12 | AC | 508 ms
193,916 KB |
testcase_13 | AC | 516 ms
196,368 KB |
testcase_14 | AC | 516 ms
197,540 KB |
testcase_15 | AC | 518 ms
198,104 KB |
testcase_16 | AC | 521 ms
198,176 KB |
testcase_17 | AC | 520 ms
198,348 KB |
testcase_18 | AC | 526 ms
198,352 KB |
testcase_19 | AC | 524 ms
198,304 KB |
testcase_20 | AC | 526 ms
198,412 KB |
testcase_21 | AC | 529 ms
198,416 KB |
testcase_22 | AC | 98 ms
42,108 KB |
testcase_23 | AC | 201 ms
80,928 KB |
testcase_24 | AC | 303 ms
120,408 KB |
testcase_25 | AC | 403 ms
159,348 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; int m = sqrt(n) + 1; vector<bool> ps(m + 1, true); ps[0] = ps[1] = false; vector<int> odd(n + 1); iota(odd.begin(), odd.end(), 0); int ans = 0; for(int i = 2; i*i <= n; ++i){ if(!ps[i]) continue; for(int j = i*i; (int64_t)j*j <= n; j += i) ps[j] = false; for(int64_t p = i*i; p <= n; p *= i*i){ for(int q = p; q <= n; q += p){ odd[q] /= i * i; } } } for(int a = 1; a <= n; ++a){ int l = n / odd[a]; int c = sqrt(l); ans += c; } cout << ans << endl; }