快速幂-UVA 10006-Carmichael Numbers

电玩女神 2022-05-16 12:21 135阅读 0赞

*  # 快速幂-UVA 10006-Carmichael Numbers #

--------------------

*  ## 题目链接：[10006 - Carmichael Numbers][] ##
 *  ## 思路： ##

对非素数n，如果满足 a^n Mod n = a(a>=2,a<=n-1)，则n为Carmichael Number，判断n是否为Carmichael Number

对于素数，直接输出Normal

不是素数，如果 a^n Mod n = a 对所有范围内的a 恒成立，则n为Carmichael Number

用Eratosthenes筛法预处理 65000内的数

**给个传送门了解下Eratosthenes筛法：[埃拉托斯特尼筛法（素数高效筛选）][Link 1]**

不是素数的就只能测试给的公式了，数据大小：(2 < n < 65000) ，果断快速幂

在求 a^n 一个a一个a地乘会超时，改用如下（记住就好了）

//避免超时
        while(n)
        {
            if(n%2)
                Res=Res*Temp_a%Mod;
            Temp_a=Temp_a*Temp_a%Mod;
            n/=2;
        }

*  ## 代码： ##

#include<iostream>
    #include<memory.h>
    using namespace std;
    #define MAX_SIZE 65005
    bool Era[MAX_SIZE];
    void Eratosthenes()   
    {
        memset(Era,true,sizeof(Era));
        for(int i=2; i*2<=MAX_SIZE; i++)
        {
            if(Era[i])
            {
                for(int j=2*i; j<MAX_SIZE; j+=i)
                    Era[j]=false;     //非素数标记为false
            }
        }
    }
    long long Quick_Mod(long long a,long long n,long long Mod)
    {
        long long Res=1;
        /*while(n--)   //会超时
        {
            Res=Res*a%Mod;
        }*/
        
        long long Temp_a=a;
        while(n)
        {
            if(n%2)
                Res=Res*Temp_a%Mod;
            Temp_a=Temp_a*Temp_a%Mod;
            n/=2;
        }
        return Res;
    }
    
    int main()
    {
        Eratosthenes();  //预处理
        long long n;
        while(cin>>n&&n)
        {
            if(Era[n])   //如果n是素数，直接输出
            {
                cout<<n<<" is normal."<<endl;
                continue;
            }
            int flag=0;
            for(long long i=2;i<=n-1;i++)
            {
                if(Quick_Mod(i,n,n)!=i)   //不满足条件，跳出
                {
                    flag=1;
                    break;
                }
            }
            if(flag==0)
                cout<<"The number "<<n<<" is a Carmichael number."<<endl;
            else
                cout<<n<<" is normal."<<endl;
        }
        return 0;
    }

[10006 - Carmichael Numbers]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=947
[Link 1]: https://blog.csdn.net/SZU_Crayon/article/details/80211628