Restructured directoriesHEADmaster

1 files changed, 32 insertions, 0 deletions

diff --git a/18/day1/tastyhay.cpp b/18/day1/tastyhay.cpp
new file mode 100644
index 0000000..8ef6d42
--- /dev/null
+++ b/18/day1/tastyhay.cpp
@@ -0,0 +1,32 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+
+int t[100001];
+map<int, ll> cnt, pre;
+
+int main() {
+    int N, Q;
+	cin >> N >> Q;
+	for (int i = 0; i < N; ++i) cin >> t[i];
+
+	unordered_map<int, int> m;
+	for (int i = N - 1; i >= 0; --i) {
+		unordered_map<int, int> tmp;
+		for (auto x : m) tmp[__gcd(t[i], x.f)] += x.s;
+		++tmp[t[i]];
+		swap(tmp, m);
+		for (auto& x : m) cnt[x.f] += x.s;
+	}
+	for (auto& x : cnt) pre[x.f] = x.s + (pre.size() ? pre.rbegin()->s : 0);
+	
+	while (Q--) {
+		int a, b;
+		cin >> a >> b;
+		auto ia = pre.upper_bound(a - 1), ib = pre.upper_bound(b);
+		cout << (ib != pre.begin() ? prev(ib)->s : 0) - (ia != pre.begin() ? prev(ia)->s : 0) << '\n';
+	}
+}
\ No newline at end of file