Add solution to 2022 Jan sleeping

1 files changed, 78 insertions, 0 deletions

diff --git a/22/feb/plat/sleeping.cpp b/22/feb/plat/sleeping.cpp
new file mode 100644
index 0000000..4f1f5c8
--- /dev/null
+++ b/22/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';
+		}
+	}
+}