폴라드 로 알고리즘으로도 25를 소인수분해할 수 있습니다. 알고리즘의 문제가 아니라 구현의 문제일 가능성이 높아보입니다.
4149번 - 큰 수 소인수분해
폴라드 로 알고리즘으로도 25를 소인수분해할 수 있습니다. 알고리즘의 문제가 아니라 구현의 문제일 가능성이 높아보입니다.
[부가 설명]
0부터 24까지의 정수를 정점으로 하여 (x, x2 + 1 mod 25)를 간선으로 하는 그래프입니다.
x0 = y0 = x, xi+1 = g(xi), yi+1 = g(g(yi))와 같이 수열을 정의할 때, xi = yi가 성립하도록 하는 자연수 i의 최솟값은 x의 값에 관계없이 정확히 3이며, 그 전에 gcd(xi, yi) = 5를 만족하는 x는 없습니다.
g(x) = x2 + 2로 놓고 돌리면 인수분해가 되기는 합니다.
근데 또 폴라드 로 또 돌리는 건 너무 귀찮아요
댓글을 작성하려면 로그인해야 합니다.
dontsaymyid 3년 전 1
25는 폴라드 로 알고리즘으로 인수분해가 불가능한 수입니다.
혹시 37%에서 시간 초과가 난다면 예외 케이스로 넣어보세요.
12조 이하의 다른 수 중에는 이런 케이스가 없었습니다.