aboutsummaryrefslogtreecommitdiff
path: root/21.5/feb/plat/sleeping.cpp
diff options
context:
space:
mode:
Diffstat (limited to '21.5/feb/plat/sleeping.cpp')
-rw-r--r--21.5/feb/plat/sleeping.cpp78
1 files changed, 78 insertions, 0 deletions
diff --git a/21.5/feb/plat/sleeping.cpp b/21.5/feb/plat/sleeping.cpp
new file mode 100644
index 0000000..4f1f5c8
--- /dev/null
+++ b/21.5/feb/plat/sleeping.cpp
@@ -0,0 +1,78 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+const int MX = 1e5+5;
+
+ll A[MX], P[MX], q[MX];
+int f[103680];
+vector<pair<ll, int>> pr;
+
+int num_factors() {
+ int ret = 1;
+ for (auto & p : pr) ret *= p.s+1;
+ return ret;
+}
+
+int & freq(ll x) {
+ ll code = 0;
+ for (auto & p : pr) {
+ int cnt = 0;
+ while (x%p.f == 0) x/= p.f, ++cnt;
+ code = (p.s+1)*code + min(p.s, cnt);
+ }
+ return f[code];
+}
+
+int main() {
+ cin.tie(0)->sync_with_stdio(0);
+ int N; cin >> N;
+ for (int i = 0; i < N; ++i) cin >> A[i];
+ partial_sum(A, A+N, P);
+ ll sum = P[N-1];
+ for (int p = 2; p < 1e6; ++p) {
+ if (sum%p == 0) {
+ int cnt = 0;
+ while (sum%p == 0) sum /= p, ++cnt;
+ pr.emplace_back(p, cnt);
+ }
+ }
+ for (int i = 0; i < N; ++i) {
+ ll tmp = gcd(P[i], sum);
+ if (tmp != 1 && tmp != sum) {
+ if (tmp > sum/tmp) tmp = sum/tmp;
+ if (tmp*tmp == sum) pr.emplace_back(tmp, 2);
+ else pr.emplace_back(tmp, 1), pr.emplace_back(sum/tmp, 1);
+ sum = 1;
+ }
+ }
+ int Q; cin >> Q;
+ for (int i = 0; i < Q; ++i) {
+ cin >> q[i];
+ ll tmp = q[i];
+ if (sum%tmp == 0 && tmp != 1 && tmp != sum) {
+ if (tmp > sum/tmp) tmp = sum/tmp;
+ if (tmp*tmp == sum) pr.emplace_back(tmp, 2);
+ else pr.emplace_back(tmp, 1), pr.emplace_back(sum/tmp, 1);
+ sum = 1;
+ }
+ }
+ if (sum > 1) pr.emplace_back(sum, 1);
+ for (int i = 0; i < N; ++i) ++freq(P[i]);
+ int block = 1;
+ for (int i = pr.size()-1; i >= 0; --i) {
+ for (int code = num_factors()-1; code >= 0; --code)
+ if (code/block%(pr[i].s+1)!=0) f[code-block] += f[code];
+ block *= pr[i].s+1;
+ }
+ for (int i = 0; i < Q; ++i) {
+ if (P[N-1]%q[i]) cout << -1 << '\n';
+ else {
+ ll ans = N+P[N-1]/q[i];
+ ans -= freq(q[i])*2;
+ cout << ans << '\n';
+ }
+ }
+}