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; } }
まとめ
日本語で書くとだいぶまどろっこしいな。