H - Carmichael Numbers(素数筛&快速幂)

题意：给定 $n$ ，若 $n$ 不为素数
且对 $\forall i\in[2,n-1],a^n\bmod n=a$ 则该数为 $Carmichael\quad Numbers$ 。

思路：因为 $n$ 只有 $65000$ 的大小，可以用素数筛预处理 $[1,65000]$ 的所有数。

接下来用快速幂的板子暴力遍历判断即可。

时间复杂度： $O(n+nloglogn)$

$ps:$ 这里复杂度可以用 $Euler$ 筛降到 $O(2n)$

AC代码：（线性筛）

#include<cstdio>
using namespace std;
const int N=65000;
int a[N+5],mod;
typedef long long ll;
void ss(int n){ //线性筛 
    a[0]=a[1]=1;
    for(int i=2;i*i<=n;i++)
        if(!a[i])
            for(int j=i*i;j<=n;j+=i) a[j]=1;
}
ll ksm(ll x,int n){//(快速幂板子) 这里x用ll因为 x*x可能会爆int  
    ll ans=1;
    while(n){
        if(n&1) ans=ans*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return ans;
}
int main(){
    int n;ss(N);
    while(~scanf("%d",&n)&&n){
        if(!a[n]){
            printf("%d is normal.\n",n);
            continue;
        }
        int f=0;mod=n;
        for(int i=2;i<n;i++)
        {
            if(ksm(i,n)!=i)
            {
                f=1;
                break;
            }
        }
        if(!f) printf("The number %d is a Carmichael number.\n",n);
        else printf("%d is normal.\n",n);
    }
    return 0;
}

AC代码：Euler筛

#include<cstdio>
using namespace std;
const int N=65000;
int a[N+5],mod,p[N];
typedef long long ll;
void ss(int n){
    for(int i=2,cnt=0;i<=n;i++)
    {
        if(!a[i]) p[cnt++]=i;
        for(int j=0;j<cnt&&p[j]*i<=n;j++)
        {
            a[i*p[j]]=1;//最小质因数筛合数。 
            if(i%p[j]==0) break;//如果i被筛过 则i*p[j+1]也被筛过了. 
        }
    } 
} 
ll ksm(ll x,int n){//(快速幂板子) 这里x用ll因为 x*x可能会爆int  
    ll ans=1;
    while(n){
        if(n&1) ans=ans*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return ans;
}
int main(){
    int n;ss(N);
    while(~scanf("%d",&n)&&n){
        if(!a[n]){
            printf("%d is normal.\n",n);
            continue;
        }
        int f=0;mod=n;
        for(int i=2;i<n;i++)
        {
            if(ksm(i,n)!=i)
            {
                f=1;
                break;
            }
        }
        if(!f) printf("The number %d is a Carmichael number.\n",n);
        else printf("%d is normal.\n",n);
    }
    return 0;
}