[SPOJ] ABCDEF – ABCDEF

原题:http://www.spoj.com/problems/ABCDEF/

---

题目大意:计算一个集合S,范围在[-30000,30000], 其中所有的可能的整数abcdef. 满足: (a*b+c)/d-e=f, where d !=0. 问多少种情况

---

分析: 公式题, 首先是整数取值, 所以就不难.先化简成a*b+c=d(e+f), 然后数一下左边集合中每个在右边的的个数. 注意:

1. 这里是每个元素, 包括重复的.
2. SPOJ真是卡空间, 用map直接TLE, 好好自己写counter吧.
3. d不能是0

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.readInt();
        }
        Arrays.sort(nums);
        int[] left = new int[n*n*n];
        int p = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                for (int k = 0; k < nums.length; k++) {
                    left[p++] = nums[i] * nums[j] + nums[k];
                }
            }
        }
        Arrays.sort(left, 0, n*n*n);
        int[][] range = new int[2][left.length];
        p = 0;
        long count = 0;
        int tmp = Integer.MAX_VALUE;
        for (int i = 0; i < left.length; i++) {
            if (tmp != left[i]){
                range[0][p] = left[i];
                range[1][p]++;
                p++;
            }
            else {
                range[1][p-1]++;
            }
            tmp = left[i];
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                for (int k = 0; k < nums.length; k++) {
                    if (nums[i] == 0)
                        continue;
                    else {
                        int right = nums[i]*(nums[j]+nums[k]);
                        int b = Arrays.binarySearch(range[0], 0, p, right);
                        if (b >= 0)
                            count+= range[1][b];
                    }
                }
            }
        }
        out.print(count);
    }