首页 > 代码库 > 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"; } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。