莫比乌斯函数与欧拉函数的单个值的快速求法

• 直接根据定义求即可，复杂度为(n)−−−√$\sqrt{(n)}$

题目：莫比与欧拉

AC程序

#include<cstdio>
#define ll int
using namespace std;
int n;
ll getphi(ll a){
    ll t=a,tmp=a;
    for(ll j=2;j*j<=tmp;j++){
        if(t%j==0) {
            a=a/j*(j-1);
            while(t%j==0) t/=j;
        }
    }if(t>1) a=a/t*(t-1);
    return a;
}
ll getmob(ll a){
    ll x=a,tmp=a;
    int cnt=0,now=0;
    for(ll j=2;j*j<=x;j++){
        now=0;
        if(x%j==0){
            while(x%j==0) now++,x/=j;
            if(now>1) return 0;
            cnt++;
        }
    }
    if(x!=1) cnt++;
    return (cnt&1)?-1:1;
}
int getmu(int n)
{
    int v=1;
    for(int i=2;i*i<=n;i++)
     if(n%i==0)
     {
        v=-v;n/=i;
        if(n%i==0)return 0;
     }
    if(n!=1)v=-v;
    return v;
}
int a;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a);
        printf("%d %d
",getphi(a),getmob(a));
    }
    return 0;
}
//不要复制粘贴