kmjp's blog

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

LeetCode Weekly Contest 418 : 3312. Sorted GCD Pair Queries

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は面倒な実装の問題はあんまり配点高くないよな…。