結果
問題 | No.1746 Sqrt Integer Segments |
ユーザー | startcpp |
提出日時 | 2021-11-18 00:43:07 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 620 ms / 2,000 ms |
コード長 | 1,669 bytes |
コンパイル時間 | 898 ms |
コンパイル使用メモリ | 85,144 KB |
実行使用メモリ | 80,216 KB |
最終ジャッジ日時 | 2023-10-11 10:37:47 |
合計ジャッジ時間 | 21,000 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 374 ms
67,476 KB |
testcase_01 | AC | 368 ms
67,424 KB |
testcase_02 | AC | 546 ms
76,408 KB |
testcase_03 | AC | 446 ms
72,420 KB |
testcase_04 | AC | 490 ms
74,020 KB |
testcase_05 | AC | 614 ms
80,060 KB |
testcase_06 | AC | 434 ms
71,400 KB |
testcase_07 | AC | 382 ms
68,720 KB |
testcase_08 | AC | 534 ms
76,216 KB |
testcase_09 | AC | 618 ms
80,052 KB |
testcase_10 | AC | 422 ms
71,052 KB |
testcase_11 | AC | 586 ms
78,816 KB |
testcase_12 | AC | 620 ms
80,200 KB |
testcase_13 | AC | 619 ms
80,168 KB |
testcase_14 | AC | 610 ms
80,216 KB |
testcase_15 | AC | 609 ms
80,104 KB |
testcase_16 | AC | 604 ms
80,148 KB |
testcase_17 | AC | 496 ms
75,100 KB |
testcase_18 | AC | 379 ms
67,620 KB |
testcase_19 | AC | 379 ms
67,708 KB |
testcase_20 | AC | 379 ms
67,668 KB |
testcase_21 | AC | 378 ms
67,420 KB |
testcase_22 | AC | 378 ms
67,412 KB |
testcase_23 | AC | 366 ms
67,420 KB |
testcase_24 | AC | 382 ms
67,680 KB |
testcase_25 | AC | 388 ms
67,756 KB |
testcase_26 | AC | 383 ms
67,704 KB |
testcase_27 | AC | 392 ms
67,692 KB |
testcase_28 | AC | 392 ms
67,620 KB |
testcase_29 | AC | 397 ms
67,724 KB |
ソースコード
//24 -> 2^3 * 3 -> 2 * 3のように置き換えてOK。 //各素因数の個数 mod 2の累積和を考えると、これをキーにして数えたいが、2 3 5 7 11 …のようなケースで膨らむ。 //集合をハッシュで管理できないか? -> ゾブリストハッシュ! //今回のように、2回同じ要素が来ると元に戻る性質のときに使えるハッシュ。 //unsigned long longで乱数生成すれば、衝突の心配も少ない。 #include <cstdio> #include <random> #include <map> #define rep(i, n) for(i = 0; i < n; i++) using namespace std; const int MAX = 1000000; int n; int a[200000]; bool isPrime[MAX + 1]; vector<int> ps[MAX + 1]; unsigned long long Rnd[MAX + 1]; mt19937_64 mt(2521); void init() { for (int i = 2; i <= MAX; i++) isPrime[i] = true; for (int i = 2; i <= MAX; i++) { if (isPrime[i]) { for (int j = i * 2; j <= MAX; j += i) { isPrime[j] = false; int tmp = j; int cnt = 0; while (tmp % i == 0) { tmp /= i; cnt++; } if (cnt % 2 == 1) { ps[j].push_back(i); } } ps[i].push_back(i); } } for (int i = 0; i <= MAX; i++) { Rnd[i] = mt(); } } map<unsigned long long, int> cnts; signed main() { int i, j; init(); scanf("%d", &n); rep(i, n) scanf("%d", a + i); unsigned long long zhash = 0; cnts[zhash]++; rep(i, n) { rep(j, ps[a[i]].size()) { int p = ps[a[i]][j]; zhash ^= Rnd[p]; } cnts[zhash]++; } long long ans = 0; for (map<unsigned long long, int>::iterator it = cnts.begin(); it != cnts.end(); it++) { int cnt = it->second; ans += (long long)cnt * (cnt - 1) / 2; } printf("%lld\n", ans); return 0; }