Collatz Conjecture

#include <iostream>
#include <unordered_set>
#include <vector>
#include <algorithm>

const int N = 5 * (1e5);
const int P = 19;
long long jump[P][N];

/*
long long gcd(long long a, long long b) {
	return std::__gcd(a, b);
	if (a < b) return gcd(b, a);
	if (b == 0) return a;
	return gcd(b, a % b);
}
*/

/*
long long gcd(long long a, long long b) {
	int twos = 0;
	while(((a | b) & 1) == 0) {
		a >>= 1;
		b >>= 1;
		++twos;
	}
	while(a != b) {
		if (a < b) std::swap(a, b);
		if (a & b & 1) {
			a = (a-b)>>1;
		} else if (a & 1) {
			b >>= 1;
		} else {
			a >>= 1;
		}
	}
	return a << twos;
}
*/


int main() {
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	int n;
	std::cin >> n;
	for (int i = 0; i < n; ++i) {
		std::cin >> jump[0][i];
	}
	for (int p = 1; p < P; ++p) {
		for (int i = 0; i < n; ++i) {
			int next = std::min(n-1, i + (1<<(p-1)));
			jump[p][i] = std::__gcd(jump[p-1][i], jump[p-1][next]);
		}
	}
	//std::vector<long long> res;
	std::unordered_set<long long> res;
	res.rehash(1e6);
	for (int s = 0; s < n; ++s) {
		long long val = jump[0][s];
		int i = s;
		// loop the times it decreases
		while(i < n) {
			if (i != s) val = std::__gcd(val, jump[0][i]);
			// loop the binary search
			int j = P-1;
			while(j && (i + (1<<j) >= n)) {
				--j;
			}
			while(i < n) {
				// loop the jump
				for (; j >= 1; --j) {
					long long sub = std::__gcd(val, jump[j][i]);
					if (sub == val) {
						break;
					}
				}
				if (j == 0) {
					i = i + 1;
					break;
				} else {
					i += (1<<j) - 1;
					--j;
				}
			}
			//res.push_back(val);
			res.insert(val);
		}
	}
	//std::sort(res.begin(), res.end());
	//res.erase(std::unique(res.begin(), res.end()), res.end());
	std::cout << res.size() << '\n';
}

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: TIME LIMIT EXCEEDED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: TIME LIMIT EXCEEDED

Test 23

Verdict: TIME LIMIT EXCEEDED

Test 24

Verdict: TIME LIMIT EXCEEDED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: TIME LIMIT EXCEEDED