### Rational zeros of a function of three variables题号：180 难度： 75 中英对照

For any integer n, consider the three functions

f1,n(x,y,z) = xn+1 + yn+1zn+1
f2,n(x,y,z) = (xy + yz + zx)*(xn-1 + yn-1zn-1)
f3,n(x,y,z) = xyz*(xn-2 + yn-2zn-2)

and their combination

fn(x,y,z) = f1,n(x,y,z) + f2,n(x,y,z) − f3,n(x,y,z)

We call (x,y,z) a golden triple of order k if x, y, and z are all rational numbers of the form a / b with
0 < a < bk and there is (at least) one integer n, so that fn(x,y,z) = 0.

Let s(x,y,z) = x + y + z.
Let t = u / v be the sum of all distinct s(x,y,z) for all golden triples (x,y,z) of order 35.
All the s(x,y,z) and t must be in reduced form.

Find u + v.

### Code

import java.util.*;

public final class p180 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}

static Set<Rational> sset = new TreeSet<Rational>();

static void addSol(Rational x, Rational y, Rational z, int n) {
Rational s = new Rational(x);
}

static long gcd(long a, long b) {
if (a == 0 || b == 0)
return a + b;
long a2 = a < 0 ? -a : a;
long b2 = b < 0 ? -b : b;
return (a2 > b2) ? gcd(a2 % b2, b2) : gcd(a2, b2 % a2);
}

public static String run(){
final int size = Rational.size;
// for each z
for (long za = 1; za <= size; za++) {
for (long zb = za + 1; zb <= size; zb++) {
if (gcd(za, zb) == 1) {
Rational z = new Rational(za, zb);
// for each x
for (long xa = 1; xa <= size; xa++) {
for (long xb = xa + 1; xb <= size; xb++) {
if (gcd(xa, xb) == 1) {
Rational x = new Rational(xa, xb);

// calculate y, y = z-x
Rational y = new Rational(z);
y.sub(x);
if (y.isValid())

// calculate y, y^2 = z^2 - x^2
Rational x2 = new Rational(x);
x2.mult(x);
Rational z2 = new Rational(z);
z2.mult(z);
y = new Rational(z2);
y.sub(x2);
if (y.trySqrt() && y.isValid())

// calculate y, y^-1 = z^-1 - x^-1
x2 = new Rational(x);
x2.recip();
z2 = new Rational(z);
z2.recip();
y = new Rational(z2);
y.sub(x2);
y.recip();
if (y.isValid())

// calculate y, y^-2 = z^-2 - x^-2
x2 = new Rational(x);
x2.recip();
x2.mult(x2);
z2 = new Rational(z);
z2.recip();
z2.mult(z2);
y = new Rational(z2);
y.sub(x2);
y.recip();
if (y.trySqrt() && y.isValid())
}
}
}
}
}
}

// compute sum
Rational t = new Rational(0, 1);
for (Rational s : sset)
long ans=t.getDen() + t.getNum();
return ""+ans;
}

static class Rational implements Comparable<Rational> {
private long num, den;
static final int size = 35;

long gcd(long a, long b) {
if (a == 0 || b == 0)
return a + b;
long a2 = a < 0 ? -a : a;
long b2 = b < 0 ? -b : b;
return (a2 > b2) ? gcd(a2 % b2, b2) : gcd(a2, b2 % a2);
}

public Rational(long x, long y) {
num = x;
den = y;
reduce();
}

public Rational(Rational r2) {
num = r2.num;
den = r2.den;
}

public void reduce() {
long g = gcd(den, num);
num /= g;
den /= g;
}

long g = gcd(den, r2.den);
num = num * (r2.den / g) + r2.num * (den / g);
den *= r2.den / g;
reduce();
}

public void sub(Rational r2) {
long g = gcd(den, r2.den);
num = num * (r2.den / g) - r2.num * (den / g);
den *= r2.den / g;
reduce();
}

public void mult(Rational r2) {
num *= r2.num;
den *= r2.den;
reduce();
}

public void recip() {
long t = num;
num = den;
den = t;
}

public boolean trySqrt() {
if (num < 0)
return false;
long n = (long) (.5 + Math.sqrt(num));
if (n * n != num)
return false;
long d = (long) (.5 + Math.sqrt(den));
if (d * d != den)
return false;
num = n;
den = d;
return true;
}

public int compareTo(Rational r2) {
long g = gcd(den, r2.den);
long d = num * (r2.den / g) - (den / g) * r2.num;
if (d < 0)
return -1;
if (d > 0)
return 1;
return 0;
}

public boolean isValid() {
return num > 0 && den > num && den <= size;
}

public String toString() {
return num + "/" + den;
}

public long getNum() {
return num;
}

public long getDen() {
return den;
}
}
}
285196020571078987
504ms