注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

projecteuler 64  

2010-10-20 14:20:41|  分类: projecteuler |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
连分数问题,问sqrt(n)的连分数(n<=10000)中循环节是奇数的有多少个
设W0=sqrt(n),连分数表示为<a0,a1,....>其中ai=floor(Wi),Wn=1/(Wn-1-an)
于是可以通过W来判断循环,不过W是浮点数,另有欧拉证明的定理存在整数gn,hn使得Wn=(gn+sqrt(n))/hn
这样避免了浮点运算精度高
import java.util.*;
import java.math.*;
public class Main {
static BigInteger a1,a2,a0,h1,h2,g1,g2,n0;
static int n;
static long solve(){
long c=0;
a0=a1=BigInteger.valueOf((long)Math.sqrt(n));
g1=BigInteger.ZERO;h1=BigInteger.ONE;
n0=BigInteger.valueOf(n);
HashMap<String,Long> m=new HashMap<String,Long>();
while(true){
++c;
g2=a1.multiply(h1).subtract(g1);
h2=(n0.subtract(g2.multiply(g2))).divide(h1);
a2=(g2.add(a0)).divide(h2);
if(m.get(g2.toString()+" "+h2.toString())!=null)
return c-m.get(g2.toString()+" "+h2.toString());
m.put(g2.toString()+" "+h2.toString(), c);
a1=a2;
g1=g2;
h1=h2;
}
}
public static void main(String[] args) {
int count=0;
for(n=1;n<=10000;++n){
if(((int)Math.sqrt(n))*((int)Math.sqrt(n))==n)
continue ;
if(solve()%2==1)
++count;
}
System.out.println(count);
}
}
  评论这张
 
阅读(327)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018