UVa NO.10006 Carmichael Numbers

UVa NO.10006

题目大意:简单的快速幂取模

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
const ll mod=1e9+7;
ll mod_pow(ll x,ll n,ll mod)
{
    ll res=1;
    while(n)
    {
        if(n&1)
            res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}
bool isPrime(int x)
{
    for(int i=2;i*i<=x;++i)
    {
        if(x%i==0)
        return 0;
    }
    return 1;
}
int main()
{
    while(~scanf("%lld",&n)&&n)
    {
        int flag=1;
        if(isPrime(n))
            flag=0;
    for(int  i=2;i<n&&flag;i++)
    {
        if(mod_pow(i,n,n)!=i)
            flag=0;
    }
    if(flag)
        printf("The number %lld is a Carmichael number.\n",n);
    else
        printf("%lld is normal.\n",n);
    }

}