반응형

문제 링크: 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)
= 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 = [2357111317192329313741]
    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

 

반응형
반응형

문제 링크: https://www.acmicpc.net/problem/5615

 

5615번: 아파트 임대

문제 동규부동산에서 아파트를 임대하고 있다. 아파트의 방은 아래 그림과 같이 면적이 2xy + x + y이다. (x와 y는 양의 정수) 동규부동산의 카탈로그에는 아파트의 면적이 오름차순으로 적혀져 있지만, 이 중 일부는 있을 수 없는 크기의 아파트이다. 만약, 이런 크기의 아파트를 임대하겠다고 말하면, 동규는 꽝! 이라고 외치면서, 수수료만 떼어간다. 동규부동산의 카탈로그에 적힌 아파트의 면적이 주어졌을 때, 있을 수 없는 크기의 아파트의 수를 구하는 프

www.acmicpc.net

<참조>

Miller-Rabin

https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

 

<문제 풀이> 수학, 정수론, Miller-Rabin(밀러-라빈) 소수 판별법

2xy + x + y = s라고 하고 인수분해 꼴로 만들면 (2x+1)(2y +1) = (2s + 1)이라고 쓸 수 있습니다.

-> (x+1)(y+1)에서 접근

 

x, y가 각각 양의 정수라고 했으므로 (2x+1) >= 3, (2y + 1) >= 3을 만족하므로 2s+1은 3이상의 두 홀수의 곱으로 표현이 되므로 소수의 정의에 의해서 절대 소수가 나올 수 없습니다.

 

따라서 2s + 1이 소수임을 판별하면 됩니다. (소수이면 있을 수 없는 아파트)

 

문제에서 s의 범위가 2^31 -1 이하이므로 2 * s + 1을 일반적인 소수 판별을 하면 시간 초과이므로 Miller-Rabin(밀러-라빈) 소수 판별법을 사용해야 됩니다.

 

<소스 코드>

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
#include <iostream>
using namespace std;
 
typedef unsigned long long ull;
 
ull power(ull x, ull y, ull p) {
    ull res = 1;
    x = x % p;
    while (y > 0) {
        if (y & 1) {
            res = (res * x) % p;
        }
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
 
bool miller_rabin(ull n, ull a) {
    ull r = 0;
    ull d = n - 1;
    while (d % 2 == 0) {
        r++;
        d = d >> 1;
    }
    ull x = power(a, d, n);
    if (x == 1 || x == n - 1return true;
    for (int i = 0; i < r - 1; i++) {
        x = power(x, 2, n);
        if (x == n - 1return true;
    }
    return false;
    
 
}
 
bool isPrime(ull n) {
    ull alist[5= { 235711 };
    if (n <= 1return false;
    if (n == 2 || n == 3return true;
    if (n % 2 == 0return false;
    for (int i = 0; i < 5; i++) {
        ull a = alist[i];
        if (n == a) return true;
        if (!miller_rabin(n, a)) return false;
    }
    return true;
 
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, cnt = 0;
    cin >> n;
    while (n--) {
        ull s;
        cin >> s;
        if(isPrime(2*s+1)) cnt++;
    }
    cout <<cnt;
    return 0;
}
 
cs

 

반응형
반응형

문제 링크: https://www.acmicpc.net/problem/4149

 

4149번: 큰 수 소인수분해

문제 큰 수를 소인수 분해 해보자. 입력 입력은 한 줄로 이루어져 있고, 소인수 분해 해야 하는 수가 주어진다. 이 수는 0보다 크고, 262보다 작다. 출력 입력으로 주어진 양의 정수를 소인수 분해 한 뒤, 모든 인수를 한 줄에 하나씩 증가하는 순서로 출력한다.  예제 입력 1 복사 18991325453139 예제 출력 1 복사 3 3 13 179 271 1381 2423...

www.acmicpc.net

<참조>

Pollrad's Rho Algorithm

https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm#The_results

https://www.geeksforgeeks.org/pollards-rho-algorithm-prime-factorization

Miller-Rabin

https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Miller%E2%80%93Rabin_test

 

<문제 풀이> 수학, 정수론, 폴라드로(Pollard-Rho), 밀러라빈(Miler-Rabin)

O(N^(1/4))에 소인수 분해를 할 수 있는 폴라드로 알고리즘을 사용하면 되는데 특정 소수에 대해서는 무한루프가 생긴다. 따라서 소수임을 O(k * log^3n) 다항 시간에 판별할 수 있는 밀러라빈 알고리즘을 함께 써야 한다.

밀러라빈을 구현할 때 빠른 거듭제곱 알고리즘 사용

 

<소스코드>

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
import sys
import random
sys.setrecursionlimit(10 ** 6)
= 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 = [2357111317192329313741]
    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
 
list.sort()
 
for i in list:
    print(i)
cs

 

 

 

반응형
반응형

문제 링크: https://www.acmicpc.net/problem/9938

 

9938번: 방 청소

문제 은기는 술병 N개(1부터 N까지 번호가 매겨져 있다)와 서랍 L개(1부터 L까지 번호가 매겨져 있다)를 가지고 있다. 술병은 은기의 방 바닥에 흩어져 있고, 어린이날을 맞이해 방 청소를 하려고 한다.  서랍에는 술병이 하나 들어갈 수 있다. 나중에 원하는 술을 빠르게 찾을 수 있게 하기 위해 은기는 각각의 술병이 들어갈 수 있는 서랍의 번호 Ai와 Bi를 공책에 적어 놓았다. 은기는 술병을 1번부터 N번까지 순서대로 정리할 것이고, 각각의 술병에 대

www.acmicpc.net

<문제 풀이> Union-Find(유니온-파인드), Disjoint-Set(서로소집합)

 

 

각 병에 대해서 A서랍, B서랍을 노드로 생각하고 그래프를 만듭니다. 여기서 부모 노드를 비어있는 서랍, 자식 노드를 병이 들어가 있는 서랍이라고 하면 그래프로 쉽게 문제를 해결할 수 있습니다.

 

서랍에 병을 넣을 때마다 넣었는지 여부를 체크해줍니다.

 

1. 서랍 A가 비어있다면 A를 자식 노드로 하고 B를 부모 노드로 한다. 

 

2. 서랍 B가 비어있다면 B를 자식 노드로 하고 A를 부모 노드로 한다.

 

3. 서랍 A에 부모 노드가 방문이 안됐으면(병을 옮길 수 있으면) 서랍 A에 부모 노드를 자식 노드로 하고 B를 부모 노드로 한다.

 

4. 서랍 B에 부모 노드가 방문이 안됐으면(병을 옮길 수 있으면) 서랍 B에 부모 노드를 자식 노드로 하고 A를 부모 노드로 한다.

 

서랍에 병이 들어있을 때 병을 다른 서랍으로 옮기는 과정들을 Union 연산으로 한 그래프를 만든다고 생각하고 빈 서랍을 찾는 데는 Find 연산으로 부모 노드를 찾는다고 생각하면 됩니다.

 

 

 

<C++ 소스 코드>

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
#include <iostream>
using namespace std;
 
int node[300001];
bool visited[300001];
 
int Find(int x) {
    if (x == node[x]) return x;
    return node[x] = Find(node[x]);
}
 
void Union(int x, int y) {
    int xParents = Find(x);
    int yParents = Find(y);
    node[xParents] = yParents;
}
 
int main(void) {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, L;
    
    cin >> N >> L;
    
    for (int i = 1; i <= L; i++) {
        node[i] = i;
    }
 
    while (N--) {
        int a, b;
        cin >> a >> b;
        if (!visited[a]) {
            visited[a] = true;
            Union(a, b); //a의 부모를 b로
            cout << "LADICA\n";
        }
        else if (!visited[b]) {
            visited[b] = true;
            Union(b, a); //b의 부모를 a로
            cout << "LADICA\n";
        }
        else if (!visited[Find(node[a])]) {
            visited[Find(node[a])] = true
            Union(a, b); //a의 부모를 b로
            cout << "LADICA\n";
        }
        else if (!visited[Find(node[b])]) {
            visited[Find(node[b])] = true;
            Union(b, a); //b의 부모를 a로
            cout << "LADICA\n";
        }
        else {
            cout << "SMECE\n";
        }
    }
 
    return 0;
}
cs

 

반응형

+ Recent posts