首页 > ACM题库 > HDU-杭电 > HDU 1905 Pseudoprime numbers-最小生成树-[解题报告] C++
2013
12-23

HDU 1905 Pseudoprime numbers-最小生成树-[解题报告] C++

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 ;
}

解题报告转自:http://blog.csdn.net/zone_programming/article/details/7581616


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

  2. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?