java - 寻找最近的非互质数

Question

给定一个数组，我需要找到最近的非互素数的索引(即 GCD(Ai, Aj) > 1 ，对于数组中的任何 Ai 和 Aj，i != j )示例，让数组为

[2 17 4 6 10]

答案是

[3 -1 4 3 4] 

我使用二进制 GCD 方法编写了这个蛮力代码(O(n^2))，这不是很有效。我想知道是否有更快的方法来做到这一点。 特别是 O(NlogN)

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Mayur Kulkarni
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        BladeReader in = new BladeReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        GCDPuz solver = new GCDPuz();
        solver.solve(1, in, out);
        out.close();
    }

    static class GCDPuz {
        public static int gcd(int p, int q) {
            if (q == 0) return p;
            if (p == 0) return q;
            // p and q even
            if ((p & 1) == 0 && (q & 1) == 0) return gcd(p >> 1, q >> 1) << 1;
                // p is even, q is odd
            else if ((p & 1) == 0) return gcd(p >> 1, q);
                // p is odd, q is even
            else if ((q & 1) == 0) return gcd(p, q >> 1);
                // p and q odd, p >= q
            else if (p >= q) return gcd((p - q) >> 1, q);
                // p and q odd, p < q
            else return gcd(p, (q - p) >> 1);
        }

        public int coprime(int p, int q) {
            if (p % 2 == 0 && q % 2 == 0) {
                return 2;
            } else if (p == q + 1 || q == p + 1) {
                return 1;
            } else {
                return gcd(p, q);
            }
        }

        public void solve(int testNumber, BladeReader in, PrintWriter out) {
            int size = in.nextInt();
            int[] arr = in.readIntArray(size);
            int[] ans = new int[size];
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == 1) {
                    ans[i] = -1;
                    continue;
                }
                int left = i == 0 ? -1 : findLeft(arr, i);
                int right = i == arr.length - 1 ? -1 : findRight(arr, i);
                int leftDist = left == -1 ? -1 : i - left;
                int rightDist = right == -1 ? -1 : right - i;
                int anss = findNearestIndex(left, leftDist, right, rightDist);
                ans[i] = anss == -1 ? -1 : anss + 1;
            }
            printa(ans, out);
        }

        private void printa(int[] ans, PrintWriter out) {
            StringBuilder sb = new StringBuilder();
            for (int an : ans) {
                sb.append(an).append(" ");
            }
            out.println(sb.toString());
        }

        private int findRight(int[] arr, int i) {
            if (arr[i] == -1) return -1;
            for (int j = i + 1; j < arr.length; j++) {
                if (coprime(arr[i], arr[j]) > 1) return j;
            }
            return -1;
        }

        private int findLeft(int[] arr, int i) {
            if (arr[i] == -1) return -1;
            for (int j = i - 1; j >= 0; j--) {
                if (coprime(arr[i], arr[j]) > 1) return j;
            }
            return -1;
        }

        private int findNearestIndex(int one, int oneDist, int two, int twoDist) {
            if (oneDist == -1 && twoDist == -1) return -1;
            if (oneDist == -1) return two;
            if (twoDist == -1) return one;
            if (oneDist == twoDist) {
                return Math.min(one, two);
            }
            return oneDist < twoDist ? one : two;
        }
    }

    static class BladeReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public BladeReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public int[] readIntArray(int size) {
            int[] array = new int[size];
            for (int i = 0; i < size; i++) {
                array[i] = nextInt();
            }
            return array;
        }
    }
}

Answer 1

如果您知道数字的最大值并且有能力保留一个素数列表，那么分解它们可能是对于平均/随机情况更好的解决方案。否则，最坏情况下的复杂度仍然是 O(N*N) - 最坏情况下认为“所有这些都是素数”。

方法:

• 分解它们并存储一个 Map<prime, multiplicity>[N] + int closestNeigh[]
• 取一个因数和O(N)为它们中的每一个确定最接近的包含该因素的因素(将涉及前缀/后缀总和)
• 从所有因素图中消除该因素
• 取下一个因素。仅当新索引最近时才调整最近邻索引。

这可能会在 O(N*<num_distict_factors>) 线上带来一些“缓解” , 但如果<num_distict_factors> == N (都是素数)，那么还是O(N*N)