FII Code 2021 Round #1 : E. Etianap

TLEスレスレだった。
https://csacademy.com/contest/fii-code-2021-round-1/task/etianap/

問題

整数列Aが与えられる。
以下のクエリに答えよ。

• 区間[x,y]と値kが与えられる。A[x...y]内でkとcoprimeな要素はいくつか。

解法

A[0...y]でcoprimeな要素数から、A[0...(x-1)]でcoprimeな要素数を引こう。
f(i,x) := A[0...i]のうちxの倍数
とすると、f(i-1,*)に対しA[i]の分を計上してf(i,*)を求めながら、各クエリを処理していこう。

kの素因数がp1,p2,p3...であるとき、A[0...i]のうちcoprimeな要素数を求めるには、包除原理の要領でf(i,1)-f(i,p1)-f(i,p2)-....+f(i,p1*p2)+f(i,p1*p3)+...を求めればよい。

const int prime_max = 1000001;
vector<int> prime;
int NP,divp[prime_max];


int N,Q;
int A[101010];
vector<int> C[1010101];

int L[101010],R[101010],K[101010];
vector<int> del[101010];
vector<int> add[101010];

ll ret[101010];
int num[1010101];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,1000001) C[i].push_back(1);
	for(i=2;i<=1000000;i++) if(divp[i]==0) {
		for(j=i;j<=1000000;j+=i) {
			divp[j]=1;
			x=C[j].size();
			FOR(y,x) C[j].push_back(C[j][y]*(-i));
		}
	}
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	cin>>Q;
	FOR(i,Q) {
		cin>>L[i]>>R[i]>>K[i];
		del[L[i]-1].push_back(i);
		add[R[i]-1].push_back(i);
	}
	
	FOR(i,N) {
		FORR(cur,del[i]) {
			FORR(v,C[K[cur]]) {
				if(v<0) ret[cur]+=num[abs(v)];
				else ret[cur]-=num[abs(v)];
			}
		}
		FORR(v,C[A[i]]) num[abs(v)]++;
		FORR(cur,add[i]) {
			FORR(v,C[K[cur]]) {
				if(v<0) ret[cur]-=num[abs(v)];
				else ret[cur]+=num[abs(v)];
			}
		}
	}
	
	FOR(i,Q) cout<<ret[i]<<endl;
	
}

まとめ

TLが厳しめだったので、値の最大値10^6じゃなく10^5位でもいいんじゃないかな…と思った。