gcdctn.cpp

#include <bits/stdc++.h>
#define MAXN 100010
#define MAXSQRT 450
using namespace std;

int n, q, arr[MAXN], buckets[MAXSQRT][MAXN], raiz;
vector <int> primos = vector <int> ({2, 3, 5, 7, 11 ,13});

int gcd(int a, int b){
	return b == 0 ? a : gcd(b, a%b);
}

int getMask(int valor){
	int mask = 0;
	for (int i=0; i<6; i++) {
		if (valor % primos[i] == 0){
			mask = mask || (1 << i);
		}
	}
	return mask;
}

void printBuc(){
	printf("------------\n");
	for (int i=0; i<4; i++){
		for (int j=0; j<10; j++){
			printf("%d ", buckets[i][j]);
		}
		printf("\n");
	}
	printf("------------\n");
}

void change(int buc, int mask, int value){
	for (int s=mask; s; s=(s-1)&mask){
		int sub = s, prod = 1, idx = 0;
		while (sub){
			prod *= (sub & 1) ?  primos[idx] : 1;
			sub = sub >> 1;
			idx++;
		}
		buckets[buc][prod] += value;
	}
//	printBuc();
}

void update(int pos, int valor){
	int buc = pos / (raiz);
	change(buc, arr[pos], -1);
	arr[pos] = valor;
	change(buc, arr[pos], 1);
}

int incluDeclu(int buc, int valor){
	int mask = getMask(valor);
	int res = 0;
	//printf("para o valor %d temos os prods = ", valor);
	for (int s=mask; s; s=(s-1)&mask){
		int sub = s, prod = 1, tam = 0, idx = 0;
		while (sub){
			prod *= (sub & 1) ? primos[idx] : 1;
			tam += (sub & 1);
			sub = sub >> 1;
			idx++;
		}
		//printf("%d ", prod);
		if (prod == 1) continue;
		if (tam & 1) res += buckets[buc][prod];
		else res -= buckets[buc][prod];
	}
	//printf("\n");
	return res;
}

int query(int de, int para, int valor){
	int res = para - de + 1;
	while (de <= para){
		int buc = de / (raiz);
		if (de % (raiz) == 0 && (de + raiz) <= para) {
			res -= incluDeclu(buc, valor);
			de += (raiz);
		} else {
			res -= (gcd(valor, arr[de]) != 1);
			de++;
		}
	}
	return res;
}

void build(){
	for (int i=0; i<n; i++){
		int buc = i / (raiz);
		change(buc, getMask(arr[i]), 1);
	}
}

int main(){
	#ifdef LOCAL
	freopen("input", "r", stdin);
	#endif

	scanf("%d", &n);
	raiz = sqrt(n);
	for (int i=0; i<n; i++){
		scanf("%d", &arr[i]);
	}

	scanf("%d", &q);

	build();
	
	int tipo, de, para, valor;
	while(q--){
		scanf("%d", &tipo);

		if (tipo == 1){
			scanf("%d %d", &de, &valor);
			de--;
			update(de, valor);
		} else if (tipo == 2){
			scanf("%d %d %d", &de, &para, &valor);
			de--, para--;
			printf("%d\n", query(de, para, valor));
		}
	}

	return 0;
}