結果
問題 | No.1746 Sqrt Integer Segments |
ユーザー | miscalc |
提出日時 | 2021-11-18 01:27:33 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 426 ms / 2,000 ms |
コード長 | 2,900 bytes |
コンパイル時間 | 2,751 ms |
コンパイル使用メモリ | 220,180 KB |
実行使用メモリ | 45,108 KB |
最終ジャッジ日時 | 2023-10-11 10:39:00 |
合計ジャッジ時間 | 11,554 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 111 ms
27,896 KB |
testcase_01 | AC | 115 ms
27,924 KB |
testcase_02 | AC | 268 ms
39,976 KB |
testcase_03 | AC | 181 ms
34,700 KB |
testcase_04 | AC | 232 ms
36,800 KB |
testcase_05 | AC | 373 ms
45,056 KB |
testcase_06 | AC | 177 ms
33,336 KB |
testcase_07 | AC | 128 ms
29,632 KB |
testcase_08 | AC | 274 ms
40,128 KB |
testcase_09 | AC | 401 ms
44,728 KB |
testcase_10 | AC | 175 ms
33,016 KB |
testcase_11 | AC | 386 ms
43,192 KB |
testcase_12 | AC | 398 ms
45,096 KB |
testcase_13 | AC | 419 ms
45,108 KB |
testcase_14 | AC | 402 ms
45,040 KB |
testcase_15 | AC | 426 ms
45,072 KB |
testcase_16 | AC | 414 ms
45,060 KB |
testcase_17 | AC | 265 ms
38,480 KB |
testcase_18 | AC | 136 ms
32,584 KB |
testcase_19 | AC | 140 ms
32,628 KB |
testcase_20 | AC | 138 ms
32,632 KB |
testcase_21 | AC | 145 ms
30,272 KB |
testcase_22 | AC | 131 ms
30,492 KB |
testcase_23 | AC | 113 ms
28,972 KB |
testcase_24 | AC | 186 ms
32,576 KB |
testcase_25 | AC | 181 ms
32,644 KB |
testcase_26 | AC | 188 ms
32,632 KB |
testcase_27 | AC | 235 ms
32,736 KB |
testcase_28 | AC | 232 ms
32,576 KB |
testcase_29 | AC | 227 ms
32,708 KB |
ソースコード
#include <bits/stdc++.h> #include <atcoder/modint> using namespace std; using namespace atcoder; using mint = modint998244353; //using mint = modint1000000007; using ll = long long; using ld = long double; using pll = pair<ll, ll>; using tlll = tuple<ll, ll, ll>; constexpr ll INF = 1LL << 60; template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;} template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;} ll safemod(ll A, ll M) {return (A % M + M) % M;} ll divfloor(ll A, ll B) {if (B < 0) {return divfloor(-A, -B);} return (A - safemod(A, B)) / B;} ll divceil(ll A, ll B) {if (B < 0) {return divceil(-A, -B);} return divfloor(A + B - 1, B);} #define FINALANS(A) do {cout << (A) << '\n'; exit(0);} while (false) class eratosthenes { public: vector<bool> isprime; vector<ll> primes; vector<ll> primeid; vector<ll> minfactor; vector<ll> mobius; eratosthenes(ll N) { isprime.assign(N + 1, true); primeid.assign(N + 1, -1); minfactor.assign(N + 1, -1); mobius.assign(N + 1, 1); isprime.at(0) = false, isprime.at(1) = false; minfactor.at(1) = 1; for (ll p = 2; p <= N; p++) { if (!isprime.at(p)) continue; primeid.at(p) = primes.size(); primes.emplace_back(p); minfactor.at(p) = p; mobius.at(p) = -1; for (ll k = 2; k * p <= N; k++) { isprime.at(k * p) = false; if (minfactor.at(k * p) == -1) minfactor.at(k * p) = p; if (k % p == 0) mobius.at(k * p) = 0; else mobius.at(k * p) *= -1; } } } vector<pll> factorize(ll n) { vector<pll> ret; while (n > 1) { ll p = minfactor.at(n); ll e = 0; while (minfactor.at(n) == p) { n /= p; e++; } ret.emplace_back(make_pair(p, e)); } return ret; } }; vector<ll> Zob; void init(ll M) { Zob.resize(M); srand((unsigned)time(NULL)); for (ll i = 0; i < M; i++) { Zob.at(i) = (rand() % (1LL << 31)) * (1LL << 31) + rand() % (1LL << 31); } } const ll M = 1000000; eratosthenes er(M); ll zobristhash(ll a) { auto pes = er.factorize(a); ll ret = 0; for (auto pe : pes) { auto [p, e] = pe; if (e % 2 == 1) { ret ^= Zob.at(er.primeid.at(p)); } } return ret; } int main() { ll N; cin >> N; vector<ll> A(N); for (ll i = 0; i < N; i++) { cin >> A.at(i); } init(er.primes.size()); vector<ll> B(N); for (ll i = 0; i < N; i++) { B.at(i) = zobristhash(A.at(i)); } vector<ll> S(N + 1); S.at(0) = 0; for (ll i = 0; i < N; i++) { S.at(i + 1) = S.at(i) ^ B.at(i); } map<ll, ll> mp; for (ll i = 0; i < N + 1; i++) { mp[S.at(i)]++; } ll ans = 0; for (auto m : mp) { ll tmp = m.second * (m.second - 1) / 2; ans += tmp; } cout << ans << endl; }