首页 > 代码库 > poj 2635 The Embarrassed Cryptographer

poj 2635 The Embarrassed Cryptographer

题目链接:http://poj.org/problem?id=2635

思路:当看到K的最大值为 10100 的第一想法就是用java打大数,建立一个素数表,然后再在素数表中去找,看是否有符合条件的。


code:

import java.math.*;
import java.util.*;

public class ggg {	
	public static void main(String[] args)
	{
		int len=0;
		Scanner cin=new Scanner(System.in);
		BigInteger prime[]=new BigInteger[80000];
		for(int i=2;i<1000010;i++)     //建立素数表
		{
			int flag=1;
			for(int j=2;j*j<=i;j++)
			{
				if(i%j==0)
				{
					flag=0;
					break;
				}
			}
			if(flag==1)
			{
				prime[len++]=BigInteger.valueOf(i);
			}
		}
		
		while(cin.hasNext())
		{
			BigInteger n,m;
			BigInteger a=new BigInteger("0");
			n=cin.nextBigInteger();
			m=cin.nextBigInteger();
			
			if(n.equals(a)&&m.equals(a))
			{
				break;
			}
			int flag=1;
			for(int i=0;i<len;i++)
			{
				if(a.equals(n.mod(prime[i])))  //判断能否被这个素数整除
				{
					if(m.compareTo(prime[i])==1)     //比较大小
					{
						flag=0;
						System.out.println("BAD "+prime[i]);
						break;
					}
				}
			}
			if(flag==1)
			{
				System.out.println("GOOD");
			}
		}		
	}
}