To_Heart—题解——ABC169 D

题目链接

题目大意

给定一个正整数\(n\),并对它进行若干次操作。
对于每次操作，选择一个正整数\(x\)，满足\(x=p^e\)且\(x\)和其它操作中用过的\(x\)不一样（每个用一次），\(x\)为n的因数。其中\(p\)为质数，\(e\)为正整数，并将\(n\)变为\(\frac{n}{x}\)
问最多操作次数。

首先对\(n\)进行质因数分解。

对于每一个\(p_i^{e_i}\),可以进一步拆分为：

所以我们要求的就是：

然后考虑怎么样让\(k_i\)最大，发现每一个\(a_i\)尽可能小的时候，\(k_i\)最大。然后就做完了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long

map<ll,ll> m;
ll tot[100005];
ll len=0;
ll n;
ll ans=0;

int main(){
//	for(int i=1;i<=50;i++)
//		Fuck
	cin>>n;
	for(ll i=2;i*i<=n;i++){
		if(n%i==0)
			tot[++len]=i;
		while(n%i==0)
			n/=i,m[i]++;
	}
	if(n>1)
		tot[++len]=n,m[n]++;
	for(int i=1;i<=len;i++){
		ll now=tot[i];
		for(int k=1;k<=m[now];k++){
			ans++;
			m[now]-=k;
		}
	}
	printf("%lld",ans);
//	for(int i=1;i<=len;i++)
//		printf("%lld %lld\n",tot[i],m[tot[i]]);
	return 0;
}

To_Heart—题解——ABC169 D

原文：https://www.cnblogs.com/xf2056188203/p/14998318.html