#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define PI 3.141592653589793 #define MAX 1000000001 const int Mod = 100000007; long long int tree[1 << 22]; long long int gcd(long long int a, long long int b) { if (b == 0) { return a; } return gcd(b, a % b); } long long int update(int nodenum, int start, int end) { if (start == end) { return tree[nodenum]; } int mid = (start + end) / 2; return tree[nodenum] = gcd(update(2 * nodenum, start, mid), update(2 * nodenum + 1, mid + 1, end)); } long long int find(int from, int to, int nodenum, int start, int end) { if (to < start || end < from) { return 0; } if (from <= start && end <= to) { return tree[nodenum]; } int mid = (start + end) / 2; return gcd(find(from, to, 2 * nodenum, start, mid), find(from, to, (2 * nodenum + 1), mid + 1, end)); } int main(void) { cin.tie(0); ios::sync_with_stdio(false); int size, n, a, b; cin >> n; size = ceil(log2(n)); size = pow(2, size); for (int i = 0; i < n; i++) { cin >> tree[size + i]; } update(1, 1, size); long long int res = 0; for (int i = 1; i <= n; i++) { long long int lo = i; long long int hi = n; long long int m = 1e9; while (lo <= hi) { long long int mid = (lo + hi) / 2; long long int g = find(i, mid, 1, 1, size); //cout << i << ' ' << mid << ' ' << g << '\n'; if (g == 1) { m = min(mid, m); hi = mid - 1; } else { lo = mid + 1; } } if (m == 1e9) { continue; } //cout << m << ' ' << i << '\n'; long long int len = n - m + 1; res += len; } cout << res << '\n'; return 0; }