111 B Petya and Divisors

問題

n個の整数の二つ組xi,yiが与えられる。それぞれについて以下のようなクエリを処理せよ。

xiの約数のうち、xi, xi-1, xi-2, ..., xi-yiのどれも割り切らないような数の個数を出力する。

制約条件

xi,yi≦10^5

方針

平方分割する。
x1〜x√nのいずれかを割る数、x√n〜x2√nのいずれかを割る数……を配列で全部覚える。
この部分にsetを使うとTLE（本番でした）なのでboolの配列にする。

ソースコード

const int SZ=350;
int n,x[100000],y[100000],k;
bool ng[SZ][100001];

bool findf(int b,int e,int m){
	
	rep(i,k){
		if(b<=i*SZ&&(i+1)*SZ<=e){
			if(ng[i][m])return 1;
		}
		else{
			for(int j=max(b,i*SZ);j<min(e,(i+1)*SZ);j++)
			if(x[j]%m==0)return 1;
		}
	}
	return 0;
}

void run(){
	cin>>n;
	rep(i,n)cin>>x[i]>>y[i];
	
	k=0;
	rep(i,n){
		for(int j=1;j*j<=x[i];j++)if(x[i]%j==0)ng[k][j]=ng[k][x[i]/j]=1;
		if(i%SZ==SZ-1)k++;
	}
	k=n/SZ+(n%SZ!=0);
	
	rep(i,n){
		set<int> st;
		for(int j=1;j*j<=x[i];j++)if(x[i]%j==0){
			if(!findf(i-y[i],i,j))st.insert(j);
			if(!findf(i-y[i],i,x[i]/j))st.insert(x[i]/j);
		}
		cout<<st.size()<<endl;
	}
}