### Investigating the Torricelli point of a triangle题号：143 难度： 65 中英对照

Let ABC be a triangle with all interior angles being less than 120 degrees. Let X be any point inside the triangle and let XA = p, XC = q, and XB = r.

Fermat challenged Torricelli to find the position of X such that p + q + r was minimised.

Torricelli was able to prove that if equilateral triangles AOB, BNC and AMC are constructed on each side of triangle ABC, the circumscribed circles of AOB, BNC, and AMC will intersect at a single point, T, inside the triangle. Moreover he proved that T, called the Torricelli/Fermat point, minimises p + q + r. Even more remarkable, it can be shown that when the sum is minimised, AN = BM = CO = p + q + r and that AN, BM and CO also intersect at T.

If the sum is minimised and a, b, c, p, q and r are all positive integers we shall call triangle ABC a Torricelli triangle. For example, a = 399, b = 455, c = 511 is an example of a Torricelli triangle, with p + q + r = 784.

Find the sum of all distinct values of p + q + r ≤ 120000 for Torricelli triangles.

### Code

public final class p143 {
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 class Pair implements Comparable<Pair>{
int x,y;
public Pair(int x,int y){
this.x=x;this.y=y;
}
public int compareTo(Pair o) {
int ans=Integer.compare(x,o.x);
if(ans!=0) return ans;
return Integer.compare(y,o.y);
}
public boolean equals(Object o){
if(o==null) return false;
if(o instanceof Pair) return this.compareTo((Pair)o)==0;
return false;
}
public String toString(){return x+","+y;}
}

static public String run(){
java.util.ArrayList<Pair> pair=new java.util.ArrayList<Pair>();
final int LIMIT=120000;
for(int u=1;u<347;u++)for(int v=1;v<u;v++){
if(gcd(u,v)!=1) continue;
if((u-v)%3==0) continue;
int a=2*u*v+v*v;
int b=u*u-v*v;
if(a+b>LIMIT) break;
for(int k=1;k*(a+b)<=LIMIT;k++){
}
}
java.util.Collections.sort(pair);
boolean vis[]=new boolean[LIMIT+1];
for(int i=0;i<vis.length;i++) vis[i]=false;
//vis用来去重
int index[]=new int[LIMIT+1];
for(int i=0;i<index.length;i++) index[i]=-1;
for(int i=0;i<pair.size();i++){
int x=pair.get(i).x;
if(index[x]==-1)
index[x]=i;
}//index[i]是标记pair中元素i开始的起点
for(int i=0;i<pair.size();i++){
Pair p=pair.get(i);
int a=p.x;
java.util.ArrayList<Integer> va=new java.util.ArrayList<Integer>();
for(int j=index[a];j<pair.size();j++){
Pair q=pair.get(j);
if(q.x!=a) break;
}
int b=p.y;
java.util.ArrayList<Integer> vb=new java.util.ArrayList<Integer>();
for(int j=index[b];j<pair.size();j++){
Pair q=pair.get(j);
if(q.x!=b) break;
}
for(int c:va){
if(vb.contains(c) && a+b+c<=LIMIT)
vis[a+b+c]=true;
}
}
long sum=0;
for(int i=0;i<vis.length;i++) if(vis[i]) sum+=i;
return ""+sum;
}
// Returns the largest non-negative integer that divides both x and y.
public static int gcd(int x, int y) {
while (y != 0) {
int z = x % y;
x = y;
y = z;
}
return x;
}

}
30758397
1451ms