给定表达式[x/2] + y + x * y, 其中x,y都是正整数。
改进了一下，不过还是要十多秒吧。package com.boco.study;import java.math.BigDecimal;import java.util.Calendar;import com.sun.java_cup.internal.internal_error;import com.sun.org.apache.xerces.internal.impl.dv.xs.YearDV;/** * 本题的奖品由亿阳信通赞助，以下是题目详情： * 给定表达式[x/2] + y + x * y, 其中x,y都是正整数。 * 其中的中括号表示下取整，例如[3/2] = 1 ， [5/2] = 2。 * 有些正整数可以用上述表达式表达出来，例如正整数2，当取x = y = 1时， * 可以把2表达出来 * （ 解释下：当x=y=1时， [x / 2] + y + x * y = [1 / 2] + 1 + 1 * 1 = 0+1+1 = 2 ）； * 有些数可以有多种方式表达，例如13可以由 x = 2 y = 4 以及x = 3 y = 3来表示； * 有些数无法用这个表达式表达出来，比如3。 * 从1开始第n个不能用这个表达式表示出来的数，我们叫做an，例如a1=1 a2=3,给定n，求an。 * 输入：n值 1<=n<=40 输出：an % 1000000007的结果（因为结果较大，输出an %1000000007的结果）。 * 函数头部 C/C++： int givean(int n); java： public class Main { public static int givean(int n) { } } 挑战规则： main函数可以不用完成，完成givean函数即可，givean函数外可编写其它函数。 获奖规则： 结合以下4点规则从答题通过者中综合评选出一二三等奖： 1、答题先后通过顺序（占30%权重） 2、代码可读性（占25%权重） 3、结合英雄榜上的排名（占15%的权重） 4、填写个人资料的完整度和真实性 N=2 an=3 N=3 an=15 N=4 an=63 N=5 an=4095 N=6 an=65535 N=7 an=262143 * @author Teakey * */public class AnNum {/** * 思路: * [x/2]+y+x*y * 令 [x/2]+y+x*y=z; * A.当x为奇数，y为奇数时。 * 令 x=2*a+1,y=2*b+1; * 限制条件：a>=0 && b>=0 * 等式 [x/2]+y+x*y=z 变化为：(4*a+3)*(a+1)=z+1; * --------------------------------------------- * B.当x为奇数，y为偶数时。 * 令x=2*a+1,y=2b; * 限制条件a>=0 && b>=1; * 等式 [x/2]+y+x*y=z 变化为：(4*a+1)*(a+1)=z+1; * ---------------------------------------------- * C.当x为偶数，y为偶数时。 * 令x=2*a y=2*b * 限制条件 a>=1 && b>=1 * 等式 [x/2]+y+x*y=z 变化为：(4*b+1)*(2*a+1)=2*z+1; * ------------------------------------------------ * D.当x为偶数，y为奇数时。 * 令x=2*a y=2*b+1 * 限制条件 a>=1 && b>=0 * 等式 [x/2]+y+x*y=z 变化为：(4*b+3)*(2*a+1)=2*z+1; * ------------------------------------------------- * 观察上面的情况，故分为a,b和c,d两种情况。 * A,B情况：有公因式a+1，结果相同：z+1； * C,D情况：有公因式2*a+1，结果相同：2*z+1. * * 不满足上面四种情况的就是要得到的数：z。 * * ------------------------------------------------ * 观察发现： * N=2 an=3=2^2-1; N=3 an=15=2^4-1; N=4 an=63=2^6-1; N=5 an=4095=2^12-1; N=6 an=65535=2^16-1; N=7 an=262143=2^18-1; 故大胆猜测所有结果均满足。2^n-1=an 所以循环的时候跨越式循环。 * * ps:还是悲剧了！大于3秒。可能每次每个数的判断方法再优化一下，可能就可以了，懒得去想了，看来我不适合追求高效率 */ public static int givean(int n) { int an=0; int bb=0; int cc=1; long lastResult=0; boolean gotit=false; for(long i=1;i<Long.MAX_VALUE&&bb<=32;i=1<<bb) { if(gotit==true) { return (int)lastResult; } bb+=2; System.out.println("Start! i="+(i-1)+" and bb="+bb); double sum=(i-1)+1; double sum2=2*(i-1)+1; Boolean findFlag=false; for(double j=0;j<=((sum+3)/4>=(sum+1)/4 ? (sum+3)/4:(sum+1)/4);j++) { if(sum%(4*j+1)==0 && (sum/(4*j+1))>=2 && j>=1){ findFlag=true; break; } if(sum%(4*j+3)==0 && (sum/(4*j+3))>=2){findFlag=true; break; } } for(double m=0;m<(((sum2/3+3)/4)>=(((sum2/3)+1)/4) ? ((sum2/3+3)/4):(((sum2/3)+1)/4)) ;m++) { if((sum2%(4*m+1)==0) && (((sum2/(4*m+1)-1)/2)>=1) && ((sum2/(4*m+1)-1)%2==0) && (sum2/(4*m+1)-1)>1 && m>=1) { findFlag=true; break; } if((sum2%(4*m+3)==0) && (((sum2/(4*m+3)-1)/2)>=1) && ((sum2/(4*m+1)-1)%2==0) && (sum2/(4*m+1)-1)>1) { findFlag=true; break; } } if(findFlag==false&&lastResult<(i-1)) { lastResult=(i-1); cc+=1; System.out.println("-------------------------I have find one!==>N="+cc+" and an="+(i-1)); an+=1; System.out.println("I have find one!==>an="+(i-1)+" and i="+an); System.out.println("现在的时间是："+System.currentTimeMillis()+""); if(an==n) { gotit=true; System.out.println("退出函数调用了！"); System.out.println(System.currentTimeMillis()+""); return (int) i%1000000007; } } // System.out.println("i="+ an +" and an="+(i)); } return (int)lastResult; } public static void main(String[] args) { long a=1; a=AnNum.givean(8); // System.out.println(Long.MAX_VALUE);//System.out.println("消耗了这么多毫秒："+(System.currentTimeMillis()-a));}}