Collatz Conjecture

#include <set>
#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 last[N];
int nxt[N];


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];
		if ((s < n-1) && (val == jump[0][s+1])) continue;
		int i = s;
		// loop the times it decreases
		while(i < n) {
			if (i != s) val = std::__gcd(val, jump[0][i]);
			if(last[i] == val) break;
			last[i] = val;
			// 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) {
					if (jump[j][i] % val == 0) break;
				}
				if (j == 0) {
					i = i + 1;
					break;
				} else {
					i += (1<<j) - 1;
					--j;
				}
			}
			//res.push_back(val);
			res.insert(val);
			if (val == 1) break;

		}
	}
	//std::sort(res.begin(), res.end());
	//res.erase(std::unique(res.begin(), res.end()), res.end());
	std::cout << res.size() << '\n';
}

Test 1

Verdict: ACCEPTED

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: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

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: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED