This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub
package library.math.largeprime; import java.math.BigInteger; import java.util.ArrayList; import java.util.Arrays; import java.util.function.LongBinaryOperator; /** * 10^18以下の整数に対して高速に素数判定や素因数分解をできるクラス */ public final class LongPrime { private static final int bsf(final long x){ return Long.numberOfTrailingZeros(x); } private static final long gcd(long a, long b) { a = Math.abs(a); b = Math.abs(b); if(a == 0) { return b; } if(b == 0) { return a; } final int shift = bsf(a|b); a >>= bsf(a); do { b >>= bsf(b); if(a > b) { a ^= b; b ^= a; a ^= b; } b -= a; } while(b > 0); return a << shift; } /** * Miller-Rabin法による素数判定 * @param n * @return 素数かどうか */ public static final boolean isPrime(final long n) { if(n <= 1) { return false; } if(n == 2) { return true; } if(n % 2 == 0) { return false; } long d = n - 1; while(d % 2 == 0) { d /= 2; } final long[] sample = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}; for(final long a: sample) { if(n <= a) { break; } long t = d; BigInteger y = BigInteger.valueOf(a).modPow(BigInteger.valueOf(t), BigInteger.valueOf(n)); while(t != n - 1 && !y.equals(BigInteger.ONE) && !y.equals(BigInteger.valueOf(n).subtract(BigInteger.ONE))) { y = y.multiply(y).mod(BigInteger.valueOf(n)); t <<= 1; } if(!y.equals(BigInteger.valueOf(n).subtract(BigInteger.ONE)) && t % 2 == 0) { return false; } } return true; } private static final long find(final long n) { if(isPrime(n)) { return n; } if(n % 2 == 0) { return 2; } long st = 0; final LongBinaryOperator f = (x, y) -> { return BigInteger.valueOf(x).multiply(BigInteger.valueOf(x)).add(BigInteger.valueOf(y)).mod(BigInteger.valueOf(n)).longValue(); }; while(true) { st++; long x = st, y = f.applyAsLong(x, st); while(true) { final long p = gcd(y - x + n, n); if(p == 0 || p == n) { break; } if(p != 1) { return p; } x = f.applyAsLong(x, st); y = f.applyAsLong(f.applyAsLong(y, st), st); } } } /** * Pollard-Rho法による素因数分解 * @param n * @return 素因数分解した結果 * @apiNote 結果はソートされていないので任意にソートすること */ public static final ArrayList<Long> primeFactor(final long n) { if(n == 1) return new ArrayList<>(); final long x = find(n); if(x == n) return new ArrayList<>(Arrays.asList(x)); final ArrayList<Long> l = primeFactor(x), r = primeFactor(n / x); l.addAll(r); return l; } }
Traceback (most recent call last): File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode() File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/languages/user_defined.py", line 68, in bundle raise RuntimeError('bundler is not specified: {}'.format(str(path))) RuntimeError: bundler is not specified: Java/library/math/largeprime/LongPrime.java