P8448 题解

· · 题解

题意

每组数据给出一个 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;
}