kmjp's blog

競技プログラミング参加記です

HourRank17 : C. GCD Matrix

3問目で手こずりすぎて時間切れ。
https://www.hackerrank.com/contests/hourrank-17/challenges/gcd-matrix

問題

N要素の数列A[i]とM要素の数列B[j]がある。
これらの数列に対し、以下のクエリQ個に応えよ。

各クエリは4値(R1,R2,C1,C2)で構成される。
R1≦i≦R2、C1≦j≦C2の範囲でGCD(A[i],B[j])は何通りの値をとるか。

解法

各B[j]に対し、B[j]の約数の集合をS[j]とする。
p∈S[j]のうち、p=GCD(A[i],B[j])を満たすA[i]が登場するかどうかを判定しよう。

各A[i]に対し約数qを列挙し、C[q]をそれぞれインクリメントしておく。
もしp∈S[j]に対しC[p]が正なら、A[i]の中にpの倍数が含まれている。
ただし、この場合正しくGCDを検出できないことがあり、A[i]=16、B[j]=12の場合、例えばp=2もp=4も「A[i]がpの倍数」を満たしてしまう。
このようなケースを正しく判定するためには、「A[i]のうちpの倍数であり、B[j]の約数のうちpを超えるpの倍数の倍数ではないものが存在する」かどうかを判定すればよい。
この時、GCD(A[i],B[j])=pを満たすものが判定する。
そのためには、(B[j]の約数のうちpを超えるpの倍数の倍数ではないもの)をrとするとC[p] - sum(C[r])が正であれば、条件を満たすA[i]が存在する。

上記のとおり各B[j]の約数pに対し、GCD(A[i],B[j])=pを満たすものがあるかどうか判定したら、あとはそのpの数を数え上げればよい。

vector<int> enumdiv(int n) {
	vector<int> S;
	for(int i=1;i*i<=n;i++) if(n%i==0) {S.push_back(i); if(i*i!=n) S.push_back(n/i); }
	sort(S.begin(),S.end());
	return S;
}

int N,M,Q;
int A[101010],B[101010];
vector<int> P[101010];
ll cnt[2][101010];
int did[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=100000;i++) P[i]=enumdiv(i);
	
	cin>>N>>M>>Q;
	FOR(i,N) cin>>A[i];
	FOR(i,M) cin>>B[i];
	
	while(Q--) {
		int R1,R2,C1,C2;
		cin>>R1>>C1>>R2>>C2;
		ZERO(cnt);
		ZERO(did);
		for(i=R1;i<=R2;i++) FORR(r,P[A[i]]) cnt[0][r]++;
		
		for(i=C1;i<=C2;i++) if(did[B[i]]==0) {
			did[B[i]]=1;
			int cc[150]={};
			x=B[i];
			for(j=P[x].size()-1;j>=0;j--) cc[j]=cnt[0][P[x][j]];
			for(j=P[x].size()-1;j>=0;j--) {
				if(cc[j]) {
					cnt[1][P[x][j]]=1;
					FOR(y,j) if(P[x][j]%P[x][y]==0) cc[y]-=cc[j];
				}
			}
		}
		int ret=0;
		for(i=1;i<=100000;i++) if(cnt[1][i]) ret++;
		cout<<ret<<endl;
		
	}
}

まとめ

日本語で書くとだいぶまどろっこしいな。