题目259：可达数

欧拉计划

Reachable Numbers

A positive integer will be called reachable if it can result from an arithmetic expression obeying the following rules:

• Uses the digits 1 through 9, in that order and exactly once each.
• Any successive digits can be concatenated (for example, using the digits 2, 3 and 4 we obtain the number 234).
• Only the four usual binary arithmetic operations (addition, subtraction, multiplication and division) are allowed.
• Each operation can be used any number of times, or not at all.
• Unary minus is not allowed.
• Any number of (possibly nested) parentheses may be used to define the order of operations.
• For example, 42 is reachable, since (1/23) * ((4*5)-6) * (78-9) = 42.
  

What is the sum of all positive reachable integers?

题目：

一个正整数如果由满足以下条件的算术表达式得到则称之为可达的。

• 使用数字 1 到 9，按照顺序并且每个数字用且只用一次。
• 任何连续的数字可以串联（例如，使用数字 2，3，4 我们将得到数字 234）。
• 只允许有 4 种基本二元算术运算（加法，减法，乘法，除法）。
• 任何一种运算可以使用任意次，或者不使用。
• 不允许一元减法。（也就是负号）
• 为了定义运算顺，可以使用任意个括号。
• 例如，42 是可达的，因为 (1/23) * ((4*5)-6) * (78-9) = 42。
  

所有可达正整数的和为多少？

天之南

import java.util.HashSet;

public class ProjectEuler_259{
        static final int LEN = 9;
        static Fraction[][][] arr = new Fraction[LEN + 1][LEN + 1][];
        static HashSet<Fraction> tmp = new HashSet<>();
        static {
                for (int i = 0; i <= LEN; i++) {
                        arr[i][i] = new Fraction[] { new Fraction(i) };
                }
        }

        public static void main(String[] args) {

                for (int len = 2; len <= LEN; len++) {
                        for (int i = 1, j = i + len - 1; j <= LEN; i++, j++) {
                                tmp.clear();
                                for (int k = i; k < j; k++) {
                                        if (len < 9)
                                                tmp.addAll(cartessian(arr[i][k], arr[k + 1][j]));
                                        else
                                                tmp.addAll(cartessianFix(arr[i][k], arr[k + 1][j]));
                                }
                                tmp.add(new Fraction(joint(i, j)));
                                arr[i][j] = new Fraction[tmp.size()];
                                tmp.toArray(arr[i][j]);
                        }
                }
                
                long sum = 0;
                for (Fraction x : arr[1][LEN]) {
                        sum += x.toLong();
                }
                System.out.println(sum);

        }

        static HashSet<Fraction> cartessian(Fraction[] a, Fraction[] b) {
                HashSet<Fraction> tmp = new HashSet<>();
                for (Fraction x : a) {
                        for (Fraction y : b) {
                                tmp.add(x.add(y));
                                tmp.add(x.mul(y));
                                tmp.add(x.sub(y));
                                if (y.n != 0)
                                        tmp.add(x.div(y));
                        }
                }
                return tmp;
        }

        static HashSet<Fraction> cartessianFix(Fraction[] a, Fraction[] b) {
                HashSet<Fraction> tmp = new HashSet<>();
                for (Fraction x : a) {
                        for (Fraction y : b) {
                                addFix(tmp, x.add(y));
                                addFix(tmp, x.mul(y));
                                addFix(tmp, x.sub(y));
                                if (y.n != 0)
                                        addFix(tmp, x.div(y));
                        }
                }
                return tmp;
        }

        static int joint(int i, int j) {
                int res = 0;
                for (int x = j, pow = 1; x >= i; x--, pow *= 10) {
                        res = res + pow * x;
                }
                return res;
        }

        static void addFix(HashSet<Fraction> set, Fraction f) {
                if (f.n > 0 && f.d == 1) {
                        set.add(f);
                }
        }

}

//分数类
class Fraction {
        public int n = 0;//分子numerator
        public int d = 1;//分母denominator

        public Fraction() {
                
        }

        public Fraction(int z) {
                this.n = z;
                this.d = 1;
        }

        // addition, subtraction, multiplication, division:加减乘除运算
        public Fraction add(Fraction x) {
                Fraction res = new Fraction();
                res.n = this.n * x.d + this.d * x.n;
                res.d = this.d * x.d;
                res.simple();
                return res;
        }

        public Fraction sub(Fraction x) {
                Fraction res = new Fraction();
                res.n = this.n * x.d - this.d * x.n;
                res.d = this.d * x.d;
                res.simple();
                return res;
        }

        public Fraction mul(Fraction x) {
                Fraction res = new Fraction();
                res.n = this.n * x.n;
                res.d = this.d * x.d;
                res.simple();
                return res;
        }

        public Fraction div(Fraction x) {
                Fraction res = new Fraction();
                res.n = this.n * x.d;
                res.d = this.d * x.n;
                res.simple();
                return res;
        }
        
        //化简
        public void simple() {
                if (n % d == 0) {
                        n = n / d;
                        d = 1;
                        return;
                }
                int min = Math.min(n, d);
                for (int i = 2; i*i <= min; i++) {
                        while (n % i == 0 && d % i == 0) {
                                n /= i;
                                d /= i;
                        }
                }
                if (d < 0) {
                        n = -n;
                        d = -d;
                }
        }

        public long toLong() {
                return n / d;
        }

        @Override
        public int hashCode() {
                final int prime = 31;
                int result = 1;
                result = prime * result + d;
                result = prime * result + n;
                return result;
        }

        @Override
        public boolean equals(Object obj) {
                if (this == obj)
                        return true;
                if (obj == null)
                        return false;
                if (getClass() != obj.getClass())
                        return false;
                Fraction other = (Fraction) obj;
                if (d != other.d)
                        return false;
                if (n != other.n)
                        return false;
                return true;
        }

        @Override
        public String toString() {
                if (d == 1)
                        return "" + n;
                return n + "/" + d;
        }
}

答案:20101196798