2013
12-23

# Pseudoprime numbers

Fermat’s theorem states that for any prime number p and for any integer a > 1, a^p == a (mod p). That is, if we raise a to the pth power and divide by p, the remainder is a. Some (but not very many) non-prime values of p, known as base-a pseudoprimes, have this property for some a. (And some, known as Carmichael Numbers, are base-a pseudoprimes for all a.)
Given 2 < p ≤ 1,000,000,000 and 1 < a < p, determine whether or not p is a base-a pseudoprime.

Input contains several test cases followed by a line containing "0 0". Each test case consists of a line containing p and a.

For each test case, output "yes" if p is a base-a pseudoprime; otherwise output "no".

3 2
10 3
341 2
341 3
1105 2
1105 3
0 0

no
no
yes
no
yes
yes

/*
---------------------------------------------------
status : a312745658	3641	Accepted	328K
16MS	C++	1732B	2012-05-18 21:36:37

stratege : 快速模取幂，素数筛选， 判断一个大数是否为素数
URL：  http://poj.org/problem?id=3641

http://acm.hdu.edu.cn/showproblem.php?pid=1905

---------------------------------------------------
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std ;

typedef long long LL ;

LL p, c ;
LL res ;

const int MAXN = 40000 ;
int isPrime [MAXN] ;
bool flag ;
LL prime[MAXN] ;
int priLen;

void getPrime ()  // 筛选40000内的素数
{
int i, j ;

memset (isPrime, 0, sizeof(isPrime)) ;
isPrime[1] = 1 ;
priLen = 1 ;
for (i = 4; i < MAXN; i += 2)
isPrime[i] = 1 ;
prime[0] = 2 ;
for (i = 3; i < MAXN; i ++)
{
if (!isPrime[i])
{
int tmp = 2 * i ;
prime[priLen ++] = i ;
while (tmp < MAXN)
{
isPrime[tmp] = 1 ;
tmp += i ;
}
}
}
}

void ModPow(LL a, LL b, LL n) //在指数p不是素数的情况下，进行快速模取幂
{
LL rec=1;
while(b)
{
if (b & 1)
rec = ((rec % n) * a) % n;
a = ((a % n) * a) % n;
b >>= 1;
}
res = rec % n;
}

bool judge (int x)  //判断指数是否为素数
{
if (x < 40000)  //小于40000直接判断
{
if (!isPrime[x])
return false ;
return true ;
}
else
{
for (int i = 0; i <= priLen && prime[i]*prime[i] <= x; i ++)
{
if (x % prime[i] == 0) //大于40000，用来除以40000以内素数
return true ;
}
return false ;  //40000内的素数都除不了，肯定是素数
}
}

int main ()
{
getPrime () ;
while (scanf ("%d%d", &p, &c), p | c)
{
flag = true ;
flag = judge (p) ;
if (!flag)
{
printf ("no\n") ;
continue ;
}

ModPow (c, p, p) ;// 快速模取幂
if (res == c)   // res == (a^p) % p
printf ("yes\n") ;
else
printf ("no\n") ;
}
return 0 ;
}

1. 您没有考虑 树的根节点是负数的情况， 若树的根节点是个很大的负数，那么就要考虑过不过另外一边子树了

2. 在方法1里面：

//遍历所有的边，计算入度
for(int i=0; i<V; i++)
{
degree = 0;