Collatz Conjecture

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

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

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 -= b;
		} else if (a & 1) {
			b >>= 1;
		} else {
			a >>= 1;
		}
	}
	return a << twos;
}

int main() {
	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] = gcd(jump[p-1][i], jump[p-1][next]);
		}
	}
	std::vector<long long> res;
	for (int s = 0; s < n; ++s) {
		long long val = jump[0][s];
		int i = s;
		// loop the times it decreases
		while(i < n) {
			val = gcd(val, jump[0][i]);
			// loop the binary search
			int j = P-1;
			while(i < n) {
				// loop the jump
				for (; j >= 1; --j) {
					if (gcd(val, jump[j][i]) == val) {
						break;
					}
				}
				if (j == 0) {
					i = i + 1;
					break;
				} else {
					i += (1<<j) - 1;
				}
			}
			res.push_back(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: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Verdict: TIME LIMIT EXCEEDED

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: TIME LIMIT EXCEEDED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: TIME LIMIT EXCEEDED

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: TIME LIMIT EXCEEDED

Test 26

Verdict: TIME LIMIT EXCEEDED