【题解】小凯的函数

qsmoonzh · 2020-01-21 11:33:08 · 个人记录

题面：小凯的函数

分析：

根据已知条件

• 当 x 为质数时有 g(x)=1。

求g(a)，我们要想办法把a变成1或质数，这样就能利用上面两个条件

然后再根据

显然是要把a进行质因数分解

思路就出来了

然后注意到范围比较大，要先把质数筛出来再进行质因数分解才能过

最后需要注意一点细节：在进行质因数分解时，要不断更新控制循环边界的变量，“up=sqrt(a);”，否则会跑很多无用的循环

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

int n,ans,z,p[80000],ip,b[1000001],up;
long long a;
int main() {
    p[++ip]=2;
    for(long long i=3; i<=1e6; i+=2) {
        if(b[i]==0) {
            p[++ip]=i;
            for(long long j=i*i; j<=1e6; j+=i)
                b[j]=1;
        }
    }
    scanf("%d",&n);
    while(n--) {
        scanf("%lld",&a);
        ans=0;
        up=sqrt(a);
        for(int j=1; p[j]<=up&&j<=ip; j++)
            if(a%p[j]==0) {
                while(a%p[j]==0) {
                    a/=p[j];
                    ans++;
                }
                up=sqrt(a);
            }
        if(a>1) ans++;
        printf("%d\n",ans);
    }
    return 0;
}