src/math/PollardRho.py

View this file on GitHub
Last update: 2023-06-10 16:58:06+09:00
Link: View error logs on GitHub Actions
Link: https://qiita.com/t_fuki/items/7cd50de54d3c5d063b4a

Depends on

src/math/MillerRabin.py

Required by

src/math/CombinationArbitrary.py

Verified with

src/$tests/math/Pollard_Rho.test.py

Code

from math import gcd

from src.math.MillerRabin import MillerRabin


def pollard(n):
    # https://qiita.com/t_fuki/items/7cd50de54d3c5d063b4a

    if n % 2 == 0:
        return 2

    m = int(n**0.125) + 1
    step = 0

    while 1:
        step += 1

        def f(x):
            return (x * x + step) % n

        y = k = 0
        g = q = r = 1

        while g == 1:
            x = y
            while k < 3 * r // 4:
                y = f(y)
                k += 1
            while k < r and g == 1:
                ys = y
                for _ in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            k = r
            r <<= 1

        if g == n:
            g = 1
            y = ys
            while g == 1:
                y = f(y)
                g = gcd(abs(x - y), n)

        if g == n:
            continue
        if MillerRabin(g):
            return g
        elif MillerRabin(n // g):
            return n // g
        else:
            return pollard(g)


def primefact(n):
    res = []
    while n > 1 and not MillerRabin(n):
        p = pollard(n)
        while n % p == 0:
            res.append(p)
            n //= p
    if n != 1:
        res.append(n)
    return sorted(res)


def primedict(n):
    P = primefact(n)
    ret = {}
    for p in P:
        ret[p] = ret.get(p, 0) + 1
    return ret

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 81, in _render_source_code_stat
    bundled_code = language.bundle(
                   ^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/python.py", line 108, in bundle
    raise NotImplementedError
NotImplementedError