[Java] Pollard-Rho Algorithm

https://aruz.tistory.com/entry/factorization-3

소인수 분해 알고리즘 #3 폴라드 로 알고리즘

이 블로그에서 정말 큰 도움을 받았다.

그런데 solve의 반복문에서 큰 차이가 있는데, 반복 횟수가 1000을 넘어갈 경우 x, y, c의 값을

랜덤하게 변경하도록 수정했다.

왜인지는 도저히 모르겠는데 같은 n의 입력에 대해서도

x, y, c에 따라 결과가 달라지는 모습이 보인다

(특정 값들에서 무한루프가 되는 모습을 보임)

 

그런데 1000을 기준으로 두어도 괜찮을지 몰라 11653번 소인수 분해에서 여러번 시험해보았는데

int 범위에서는 1000을 기준으로 두어도 괜찮은듯 하다.

처음에는 100,000까지 올렸었는데, 1,000으로 기준을 내리니 시행속도도 그럭저럭

 

import java.util.*;
import java.io.*;

public class pollard_rho {
    static FastScanner fs = new FastScanner();
    static PrintWriter pw = new PrintWriter(System.out);
    static Map<Long, Integer> facs;
    static Random rand = new Random();

    public static void main(String[] args) {
        int t = 1;
        while (t-- > 0){
            facs = new TreeMap<>();
            solve(fs.nextLong());
            for (Long i : facs.keySet()){
                int cnt = facs.get(i);
                while (cnt-- > 0) pw.println(i);
            }
        }

        pw.close();
    }

    static void solve(long n){
        if (n == 1) return;
        if ((n & 1) == 0){
            facsAdd(2);
            solve(n / 2);
            return;
        }
        if (isPrime(n)){
            facsAdd(n);
            return;
        }

        long x = -1, y = -1, c = -1, d = n;
        int cnt = 0;
        do {
            cnt++;
            if (d == n || cnt > 1000){
                x = rand.nextInt(100) % (n - 2);
                y = rand.nextInt(100) % (n - 2);
                c = rand.nextInt(100) + 1;
                d = 1;
            }

            x = f(x, c, n);
            y = f(f(y, c, n), c, n);
            long a1 = (long)Math.abs(x - y), a2 = n;
            d = gcd(Math.min(a1, a2), Math.max(a1, a2));
        } while (d == 1);

        solve(d);
        solve(n / d);
    }

    static long gcd(long a, long b){
        if (a == 0) return b;
        return gcd(b % a, a);
    }

    static long f(long x, long c, long n){
        return ((long)Math.pow(x, 2) + c) % n;
    }

    static void facsAdd(long n){
        if (!facs.containsKey(n)){
            facs.put(n, 0);
        }
        facs.put(n, facs.get(n) + 1);
    }

    static boolean isPrime(long n){
        if (n == 1) return false;
        for (long i=2;i*i<=n;i++){
            if (n % i == 0) return false;
        }
        return true;
    }

    // ----------input function----------

    static void sort(int[] a) {
        ArrayList<Integer> L = new ArrayList<>();
        for (int i : a)
            L.add(i);
        Collections.sort(L);
        for (int i = 0; i < a.length; i++)
            a[i] = L.get(i);
    }

    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next() {
            while (!st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

        double nextDouble() {
            return Double.parseDouble(next());
        }

        int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}