自动搬运

查看原文

来自洛谷，原作者为

	Quidrem 抱歉，是在下无敌了

搬运于2025-08-24 22:39:09，当前版本为作者最后更新于2022-07-26 21:49:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

每组数据给出一个 $n$（long long 范围内），重复将 $n$ 整除一个可以表示为 $y^z$ 的数（$x,z$ 为质数且 $z\neq 2$），直到无法再找到这样的数。求出最多能整除多少个这样的数。

思路

为了使整除的个数多，就需要使 $z$ 尽量小（这样每次 $n$ 除去的数 $y^z$ 就会保证最小，可供整除操作的次数最大）。

因为符合条件的最小 $z=3$，所以我们只需要枚举质数 $y$，并判断 $y^3$ 是不是 $n$ 的因数，若是则循环把 $n$ 除去这个数直到 $n$ 不再是这个数的倍数即可。

当我们将 $n$ 因数中包含的一个质数（不妨设其为 $y_i$）的三次方除尽后，$n$ 一定不再会是 $(ky_i)^3$ 的倍数（其中 $k$ 为大于 $1$ 的正整数），所以我们只要从 $2$ 开始枚举 $y$，每次 $y$ 加 $1$ 就行了，这样就免去了筛素数的步骤。

注：本题思路较为简单，就不列出公式来表达意义了，以免混淆各位的思维。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll t,n,ans;
int main(){
	scanf("%lld",&t);
	while(t--){
		scanf("%lld",&n);
		ans=0;
		for(ll i=2;i*i*i<=n;i++){
			while(n%(i*i*i)==0)n/=i*i*i,ans++;
		}
		printf("%lld\n",ans);
	}
	return 0;
}