P8448题解

ztntonny · 2022-07-26 21:33:30 · 题解

题意

给一个数 n，问能用几个形如 y^z 的数整除 n（y，z 均为质数，z 为奇数）。

思路

本人的代码跑出 12ms，是最快的了，首先打一个小质数表，本人试过 13 个刚好，然后每次进来数后双层暴力嵌套循环枚举 y^z，加上剪枝即可。因为最小的奇数质数为 3，所以最多到 \sqrt[3]{n}。

#include <bits/stdc++.h>
using namespace std;
int n[13]={2,3,5,7,11,13,17,19,23,29,31,37,41};//质数表
int main()
{
    ios::sync_with_stdio(false);//加速输入
    long long a , b , h , s , i;
    cin >> a;
    while ( cin >> b )
    {
        h = 0;//一定初始化计数器
        for ( i = 0; i < 13 && n[i] * n[i] * n[i] <= b; i++ )//剪枝（因为最小的奇质数为3，所以到三次根号b就停）
        {
            s = 0;
            while ( b % n[i] == 0 )//暴力枚举整除次数
            {
                b /= n[i];
                s++;
            }
            h += s / 3;//因为最小的奇质数为3，所以加上除以三就行了
        }
        cout << h << endl;
    }
}