UVa10006-Carmichael Numbers

快速冪取模

code:

[cpp] 
#include <iostream>  
#include <cstring>  
#include <cmath>  
using namespace std; 
typedef long long LL; 
LL pow_mod(LL a, LL b, LL m) 
{ 
    LL res = 1; 
    for(;b;b>>=1,a=(a*a)%m) 
        if(b&1) res =(res*a) %m; 
    /*while(b)
    {
        if(b&1) res =res*a %m;
        a = a*a % m;
        b >>=1;
    }*/ 
    return res; 
} 
#define N 65000  
bool prime[N]; 
void sieve_prime() 
{ 
    memset(prime,1,sizeof(prime)); 
    for(int i=2;i<=sqrt(N); i++) 
    if(prime[i]) 
    for(int j=i*i; j<=N; j+=i) 
        prime[j] = 0; 
} 
int main() { 
    int n; 
    sieve_prime(); 
    while(cin>>n,n) { 
        if(prime[n]) 
        { 
           cout<<n<<" is normal."<<endl; 
           continue; 
        } 
        bool flag = 1; 
        for(int i=2; i<n; i++) { 
            if(pow_mod(i,n,n)!=i) { 
                flag = 0; 
                break; 
            } 
        } 
        if(flag) cout<<"The number "<<n<<" is a Carmichael number."<<endl; 
        else 
            cout<<n<<" is normal."<<endl; 
    } 
} 

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
LL pow_mod(LL a, LL b, LL m)
{
    LL res = 1;
    for(;b;b>>=1,a=(a*a)%m)
        if(b&1) res =(res*a) %m;
    /*while(b)
    {
        if(b&1) res =res*a %m;
        a = a*a % m;
        b >>=1;
    }*/
    return res;
}
#define N 65000
bool prime[N];
void sieve_prime()
{
    memset(prime,1,sizeof(prime));
    for(int i=2;i<=sqrt(N); i++)
    if(prime[i])
    for(int j=i*i; j<=N; j+=i)
        prime[j] = 0;
}
int main() {
    int n;
    sieve_prime();
    while(cin>>n,n) {
        if(prime[n])
        {
           cout<<n<<" is normal."<<endl;
           continue;
        }
        bool flag = 1;
        for(int i=2; i<n; i++) {
            if(pow_mod(i,n,n)!=i) {
                flag = 0;
                break;
            }
        }
        if(flag) cout<<"The number "<<n<<" is a Carmichael number."<<endl;
        else
            cout<<n<<" is normal."<<endl;
    }
}