UVa10006-Carmichael Numbers

快速幂取模

code:

[cpp]
#include
#include
#include
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< continue;
}
bool flag = 1;
for(int i=2; i if(pow_mod(i,n,n)!=i) {
flag = 0;
break;
}
}
if(flag) cout<<"The number "< else
cout< }
}

#include
#include
#include
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< continue;
}
bool flag = 1;
for(int i=2; i if(pow_mod(i,n,n)!=i) {
flag = 0;
break;
}
}
if(flag) cout<<"The number "< else
cout< }
}