当前位置:首页 » Project Euler » 详细页

Odd period square roots 题号:64 难度: 20 中英对照

All square roots are periodic when written as continued fractions and can be written in the form:

N = a0 +
1

Solution

此道题目显示有问题,请打开中英对照,查看题目 每个时刻的分数都可以表示为 $\frac{a+b\sqrt{d}}{c}$ 的形式,以$\sqrt{23}$为例: $$ \sqrt{23}=\frac{0+1\sqrt{23}}{1} (a=0,b=1,c=1,d=23),因为floor(\sqrt23)=4,所以a_0=4,下一分数为\frac{1}{\sqrt{23}-4} $$ $$ \frac{1}{\sqrt{23}-4}=\frac{4+\sqrt{23}}{7} (a=4,b=1,c=7,d=23),因为floor(\frac{4+\sqrt{23}}{7} )=1,所以a_1=1,下一分数为\frac{1}{\frac{\sqrt{23}+4}{7}-1}=\frac{7}{\sqrt{23}-3} $$ $$ \frac{7}{\sqrt{23}-3}=\frac{21+7\sqrt{23}}{14} (a=21,b=17,c=14,d=23),因为floor(\frac{21+7\sqrt{23}}{14} )=3,所以a_2=3,下一分数为\frac{1}{\frac{21+7\sqrt{23}}{14}-3}=\frac{2}{\sqrt{23}-3} $$ $$ ... $$ $$ \frac{1}{\sqrt{23}-4}=\frac{4+\sqrt{23}}{7} (a=4,b=1,c=7,d=23),因为floor(\frac{4+\sqrt{23}}{7} )=1,所以a_5=1,下一分数为\frac{1}{\frac{\sqrt{23}+4}{7}-1}=\frac{7}{\sqrt{23}-3} $$ 当迭代到要计算$a_5$时,发现$a、b、c、d$的值已经和要计算 $a_1$ 时是重复,因此接下来的$a_i$都会以$[a_1,a_2 ,a_3,a_4]$ 的形式循环出现。因此,我们每次迭代一个数的连分数时候,只需要判断 $a、b、c、d$ 是否重复就能得到周期数。 算法的步骤如下: 1.对每一个不大于 $10000$ 的正整数N,迭代地计算连分数$a_i$,每计算一次,更新对应的$a、b、c、d$ 值,周期计数加 $1$,直到$a、b、c、d$值重复为止。 2.通过步骤1,就得到$10000$以内所有正整数的周期数。再进行一次遍历,对那些周期为奇数的数进行计数。最后返回计数结果即可。

Code

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public final class p64{
	
	public static void main(String[] args) {
		long start = System.nanoTime();
		int result = run();
        long end = System.nanoTime();
		System.out.println( result );
		System.out.println (( end - start )/1000000 +"ms");
	}
	
	
	public static int run() {
		int count = 0;
		for (int i = 1; i <= 10000; i++) {
			if (!isSquare(i) && getSqrtContinuedFractionPeriod(i) % 2 == 1)
				count++;
		}
		return count;
	}
	
	
	// 得到sqrt(n)的连分数周期数
	private static int getSqrtContinuedFractionPeriod(int n) {
		Map<QuadraticSurd,Integer> seen = new HashMap<>();
		QuadraticSurd val = new QuadraticSurd(BigInteger.ZERO, BigInteger.ONE, BigInteger.ONE, BigInteger.valueOf(n));
		do {
			seen.put(val, seen.size());
			val = val.subtract(new QuadraticSurd(val.floor(), BigInteger.ZERO, BigInteger.ONE, val.d)).reciprocal();
		} while (!seen.containsKey(val));
		return seen.size() - seen.get(val);
	}
	
	
	//表示 (a + b * sqrt(d)) / c ,d不能为一个完全平方数
	private static class QuadraticSurd {
		
		public final BigInteger a, b, c, d;
		
		
		public QuadraticSurd(BigInteger a, BigInteger b, BigInteger c, BigInteger d) {
			if (c.signum() == 0)
				throw new IllegalArgumentException();
			
			// 化简,除去最大公约数
			if (c.signum() == -1) {
				a = a.negate();
				b = b.negate();
				c = c.negate();
			}
			BigInteger gcd = a.gcd(b).gcd(c);
			if (!gcd.equals(BigInteger.ONE)) {
				a = a.divide(gcd);
				b = b.divide(gcd);
				c = c.divide(gcd);
			}
			
			this.a = a;
			this.b = b;
			this.c = c;
			this.d = d;
		}
		
		//相减后,a、b、c、d值的更替
		public QuadraticSurd subtract(QuadraticSurd other) {
			if (!d.equals(other.d))
				throw new IllegalArgumentException();
			return new QuadraticSurd(a.multiply(other.c).subtract(other.a.multiply(c)), b.multiply(other.c).subtract(other.b.multiply(c)), c.multiply(other.c), d);
		}
		
		
		//求倒数
		public QuadraticSurd reciprocal() {
			return new QuadraticSurd(a.multiply(c).negate(), b.multiply(c), b.multiply(b).multiply(d).subtract(a.multiply(a)), d);
		}
		
		//
		public BigInteger floor() {
			BigInteger temp = sqrt(b.multiply(b).multiply(d));
			if (b.signum() == -1)
				temp = temp.add(BigInteger.ONE).negate();
			temp = temp.add(a);
			if (temp.signum() == -1)
				temp = temp.subtract(c.subtract(BigInteger.ONE));
			return temp.divide(c);
		}
		
		
		public boolean equals(Object obj) {
			if (!(obj instanceof QuadraticSurd))
				return false;
			else {
				QuadraticSurd other = (QuadraticSurd)obj;
				return a.equals(other.a) && b.equals(other.b) && c.equals(other.c) && d.equals(other.d);
			}
		}
		
		public int hashCode() {
			return a.hashCode() + b.hashCode() + c.hashCode() + d.hashCode();
		}
		
	}
	//判断一个数是不是完全平方数
	public static boolean isSquare(int x) {
		if (x < 0)
			return false;
		int y = (int) Math.sqrt(x);
		return y * y == x;
	}
	//大数的平凡根floor(sqrt(x))
	public static BigInteger sqrt(BigInteger x) {
		if (x.signum() == -1)
			throw new IllegalArgumentException("Square root of negative number");
		BigInteger y = BigInteger.ZERO;
		for (int i = (x.bitLength() - 1) / 2; i >= 0; i--) {
			y = y.setBit(i);
			if (y.multiply(y).compareTo(x) > 0)
				y = y.clearBit(i);
		}
		return y;
	}
	
}
1322
858ms