首页 > ACM题库 > HDU-杭电 > hdu 2012 素数判定-数论-[解题报告]C++
2013
12-26

hdu 2012 素数判定-数论-[解题报告]C++

素数判定

问题描述 :

对于表达式n^2+n+41,当n在(x,y)范围内取整数值时(包括x,y)(-39<=x<y<=50),判定该表达式的值是否都为素数。

输入:

输入数据有多组,每组占一行,由两个整数x,y组成,当x=0,y=0时,表示输入结束,该行不做处理。

输出:

输入数据有多组,每组占一行,由两个整数x,y组成,当x=0,y=0时,表示输入结束,该行不做处理。

样例输入:

0 1
0 0

样例输出:

OK

题意:给出p,a问p是不是以a为底的伪素数,如果p不是素数判断,是否a^p%p==a






#include<iostream>  
#include<algorithm>  
#include<math.h>  
#include<stdio.h>    
#include<string.h>    
#include<time.h>    
#include<stdlib.h>    
typedef __int64 LL;   
LL a,b,sum;   
const int S=20;//随机算法判定次数,S越大,判错概率越小     
//***************Miller_Rabin 算法进行素数测试***************    
int cmp(void const *a,void const *b)  
{  
    if(*(LL *)a>*(LL *)b)  
        return 1;  
    else return -1;  
}  
LL mult_mod(LL a,LL x,LL n)//返回(a*x) mod n,a,x,n<2^63    
{    
    a%=n;x%=n;    
    LL ret=0;    
    while(x)    
    {    
        if(x&1){ret+=a;if(ret>=n)ret-=n;}    
        a<<=1;    
        if(a>=n)a-=n;    
        x>>=1;    
    }    
    return ret;    
}    
LL pow_mod(LL a,LL x,LL n)//返回a^x mod n    
{    
    if(x==1)return a%n;    
    int bit[70],k=0;    
    while(x)    
    {    
        bit[k++]=(x&1?1:0);    
        x>>=1;    
    }    
    LL ret=1;    
    for(--k;k>=0;k--)    
    {    
       ret=mult_mod(ret,ret,n);    
       if(bit[k])ret=mult_mod(ret,a,n);    
    }    
    return ret;    
}    
bool judge(LL a,LL n,LL x,LL t)//以a为基,n-1=x*2^t,检验n是不是合数    
{    
    LL ret=pow_mod(a,x,n),flag=ret;    
    for(LL i=1;i<=t;i++)    
    {    
        ret=mult_mod(ret,ret,n);    
        if(ret==1&&flag!=1&&flag!=n-1)return true;    
        flag=ret;    
    }    
    if(ret!=1)return true;    
    return false;    
}    
bool Miller_Rabin(LL n)    
{    
    if(n==2||n==5||n==7||n==11)return true;    
    if(n%2==0||n%5==0||n%7==0||n%11==0)return false;    
    LL x=n-1,t=0;    
    while((x&1)==0)x>>=1,t++;    
    bool flag=true;    
    if(t>=1&&(x&1)==1)    
    {    
        for(int i=1;i<=S;i++)    
        {    
            LL a=rand()%(n-1)+1;    
            if(judge(a,n,x,t)){flag=true;break;}    
            flag=false;    
        }    
    }    
    if(flag)return false;    
    else return true;    
}
int main()
{
	int i,j;
	LL p,a,b;
	while(scanf("%I64d %I64d",&p,&a),p||a)
	{
		if(Miller_Rabin(p)){printf("no\n");continue;}
		b=pow_mod(a,p,p);
		if(b==a)
			printf("yes\n");
		else printf("no\n");
	}
	return 0;
}

解题转自:http://blog.csdn.net/aixiaoling1314/article/details/12977123


  1. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。

  2. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。