首页 > 代码库 > ZOJ ACM 2060(JAVA)

ZOJ ACM 2060(JAVA)

题目描述请参考:ZOJ ACM 2060

1)难度分析

由于N较大,为1000000,如果用递归中规中矩的计算结果后再判断是否被3整除肯定超时且费内存。

2)解决方法

f(0) %3 = 1; f(1) %3 = 2; f(2) % 3 = 0;...

通过简单观察,可以发现这是有规律的,因为3比较小,所以并不需要太久即可完成一个循环。从而根据N直接判断是否可被3整除。

结果如下:

f(0) % 3 = 1;  f(1) % 3 = 2;  f(2) % 3 = 0;  f(3) % 3 = 2;  f(4) % 3 = 2;  f(5) % 3 = 1;  f(6) % 3 = 0;  f(7) % 3 = 1; 

f(8) % 3 = 1;  f(9) % 3 = 2;  f(10) % 3 = 0;...

由此可以知道当f(n)的n为8的倍数,即可完成一次循环。其中n%8=2和6的时候,f(n)%3=0;

3)AC 源码

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		java.util.Scanner scanner = new java.util.Scanner(System.in);
		
		while(scanner.hasNext()) {
			long N = Integer.parseInt(scanner.nextLine());
			System.out.println(canDivEvenlyByThree(N));
		}
		
	}
	
	public static String canDivEvenlyByThree(long n) {
		if(n % 8 == 2 || n % 8 == 6)
			return "yes";
		return "no";
	}
}