1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
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';
}
}
}
|
