### 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

### 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) {
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不能为一个完全平方数

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值的更替
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);
}

//求倒数
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)
if (temp.signum() == -1)
temp = temp.subtract(c.subtract(BigInteger.ONE));
return temp.divide(c);
}

public boolean equals(Object obj) {
return false;
else {
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