题解：P13016 [GESP202506 六级] 最大因数

题目传送门

思路

设

k

质因数分解后的

k=\Pi_{i=1}^m\alpha_i

(

\alpha

从小到大排，可重复)，那么根据整数的唯一分解定理，显然它的第

\beta

级祖先为

\Pi_{i=\beta+1}^m\alpha_i

。那就好做了，先给

x

和

y

质因数分解，存到 mp[0] 和 mp[1] 里面，计算交集 s，想算 LCA 那么只需要计算交集里最大的下标

id

使得 mp[0][s[id]] 和 mp[1][s[id]] 不相等即可。答案就是

\sum_{i=1}^{id-1}mp_{0,s_i}+mp_{1,s_i}+|mp_{0,s_{id}}-mp_{1,s_{id}}|

，时间复杂度

O(q\sqrt n\log\sqrt n)

，

\log

是 map 贡献的。

Code

CPP

#include <bits/stdc++.h>
using namespace std;
#define il inline
#define fst first
#define sed second
#define ins insert
#define cl clear
map<int, int> mp[2];
set<int> s;
il void qwq(int x, int id)
{
	for(int i = 2;i <= x / i;++i)
	{
		while(x % i == 0)
		{
			mp[id][i]++;
			s.ins(i);
			x /= i;
		}
	}
	if(x > 1)
	{
		mp[id][x]++;
		s.ins(x);
	}
}
int main()
{
	int q;cin >> q;
	while(q--)
	{
		s.cl(), mp[0].cl(), mp[1].cl();
		int x, y;cin >> x >> y;
		if(x == y)
		{
			cout << "0\n";
			continue;
		}
		qwq(x, 0);qwq(y, 1);
		int cnt = 0, id = 0;
		for(auto i : s)
			if(mp[0][i] != mp[1][i]) id = i;
		for(auto i : s)
		{
			if(i > id) break;
			if(i == id) cnt += abs(mp[0][i] - mp[1][i]);
			else cnt += mp[0][i] + mp[1][i];
		}
		cout << cnt << "\n";
	} 
	return 0;
}

题解：P13016 [GESP202506 六级] 最大因数

文章操作

题目传送门

思路

Code

相关推荐

评论

题解：P13016 [GESP202506 六级] 最大因数