반응형
문제 링크: https://www.acmicpc.net/problem/10854
10854번: Divisions
David is a young boy and he loves numbers. Recently he learned how to divide two numbers. David divides the whole day. He is happy if the result of the division is an integer, but he is not very amused if this is not the case. After quite a while he decide
www.acmicpc.net
<참조>
https://seokjin2.tistory.com/5
<문제 풀이> 수학, 정수론, 폴라드로(Pollard-Rho), 밀러라빈(Miler-Rabin)
폴라드로 알고리즘으로 O(N^(1/4))에 소인수 분해하고 약수의 개수를 구하면 된다.
n == 1일 때 따로 처리
<소스 코드>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
import sys
import random
sys.setrecursionlimit(10 ** 6)
n = int(input())
def power(x, y, p):
res = 1
x = x % p
while y > 0:
if y & 1:
res = (res * x) % p
y = y >> 1
x = (x*x) % p
return res
def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
r = a % b
a = b
b = r
return a
def miller_rabin(n, a):
r = 0
d = n-1
while d % 2 == 0:
r += 1
d = d//2
x = power(a, d, n)
if x == 1 or x == n-1:
return True
for i in range(r-1):
x = power(x, 2, n)
if x == n - 1:
return True
return False
def is_prime(n):
alist = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
if n == 1:
return False
if n == 2 or n == 3:
return True
if n % 2 == 0:
return False
for a in alist:
if n == a:
return True
if not miller_rabin(n, a):
return False
return True
def pollardRho(n):
if is_prime(n):
return n
if n == 1:
return 1
if n % 2 == 0:
return 2
x = random.randrange(2, n)
y = x
c = random.randrange(1, n)
d = 1
while d == 1:
x = ((x ** 2 % n) + c + n) % n
y = ((y ** 2 % n) + c + n) % n
y = ((y ** 2 % n) + c + n) % n
d = gcd(abs(x - y), n)
if d == n:
return pollardRho(n)
if is_prime(d):
return d
else:
return pollardRho(d)
list = []
while n > 1:
divisor = pollardRho(n)
list.append(divisor)
n = n // divisor
if len(list) > 0:
list.sort()
prev = list[0]
cnt = 0
res = 1
for i in list:
if i == prev:
cnt += 1
else:
res *= (cnt + 1)
cnt = 1
prev = i
res *= (cnt + 1)
print(res)
else:
print(1)
|
cs |
반응형
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
| [백준 2749번] 피보나치 수 3 (0) | 2020.02.29 |
|---|---|
| [백준 10830번] 행렬 제곱 - (빠른 거듭제곱 알고리즘) (2) | 2020.02.28 |
| [백준 5615번] 아파트 임대 (0) | 2020.02.22 |
| [백준 4149번] 큰 수 소인수분해 - 폴라드로(PollardRho) + 밀러라빈(MillerRabin) (0) | 2020.02.21 |
| [백준 9938번] 방 청소 (0) | 2020.02.15 |