Q3の方が難しいような。
https://leetcode.com/problems/sorted-gcd-pair-queries/description/
問題
50000以下の要素で構成される整数列Aが与えられる。
2要素のGCDを、全通り昇順に並べた数列を考える。
クエリとしてそのindexが指定されるので、数列のそのindexの値を答えよ。
解法
最初に、GCDが1~50000それぞれになるケースが何通りか列挙してしまおう。
F(n) := Aのうちnの倍数の要素数
G(n) := 2要素のGCDのうち、nの倍数となる組み合わせ
H(n) := 2要素のGCDのうち、nとなる組み合わせ
F(n)はAを走査すれば求まるし、G(n)=F(n)*(F(n)-1)/2で計算できる。
H(n)はG(n)を約数包除すればよい。
あとはHの累積和を取って、各クエリに対し二分探索をすればよい。累積和取らずに、クエリをソートして尺取り法でもよい。
ll C[505050]; ll P[505050]; ll S[505050]; map<int,vector<int>> M; vector<int> enumdiv(int n) { if(M.count(n)==0) { 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); } M[n]=S; } return M[n]; } class Solution { public: vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) { int i,j; FOR(i,50505) C[i]=P[i]=0; FORR(a,nums) { auto V=enumdiv(a); FORR(v,V) P[v]+=C[v]++; } for(i=50000;i>=1;i--) { for(j=i*2;j<=50000;j+=i) P[i]-=P[j]; } for(i=1;i<=50000;i++) S[i]=S[i-1]+P[i]; vector<int> R; FORR(q,queries) { R.push_back(lower_bound(S,S+50001,q+1)-S); } return R; } };
まとめ
LeetCodeは面倒な実装の問題はあんまり配点高くないよな…。