중국인의 나머지 정리는, 어떤 수 x를 서로소인 m1, m2, m3, ..., mn으로 각각 나눴을 때 나머지가 a1, a2, a3, ..., an 이라고 할 때 x는 m1* m2 * m3 * ... * mn 의 modular 연산 안에서 해가 유일하다는 것을 말한다. 


https://librewiki.net/wiki/%EC%A4%91%EA%B5%AD%EC%9D%B8%EC%9D%98_%EB%82%98%EB%A8%B8%EC%A7%80_%EC%A0%95%EB%A6%AC


http://blog.naver.com/PostView.nhn?blogId=rym&logNo=220833505480&categoryNo=0&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postView

'Study > Algorithms' 카테고리의 다른 글

[Algorithm] 오일러 파이(피) 함수 Euler's phi function  (0) 2017.08.31
[Algorithm] 확장 유클리드 알고리즘 Extended Euclid Algorithm  (0) 2017.08.31
[Algorithm] Convex Hull Algorithm  (0) 2017.08.24
[Algorithm] CCW Algorithm [펌]  (0) 2017.08.24

http://codepractice.tistory.com/79




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
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
 
using namespace std;
 
int RecursiveEuclid(int a, int b)
{
    if (a < b)
        swap(a, b);
 
    if (a%b == 0)
        return b;
    else
        return RecursiveEuclid(b, a%b);
}
 
template<typename T>
T LoopEuclid(T a, T b)
{
    if (a < b)
        swap(a, b);
 
    while (a%b != 0)
    {
        T tmp = a;
        a = b;
        b = tmp%b;
    }
    return b;
}
 
 
template<typename T>
pair<T, T> ExtendedEuclid(T a, T b)
{
    T q = (a / b);
    T r = a%b;
    T s1, s2, t1, t2;
    s1 = 0;
    t1 = 1;
    s2 = 1;
    t2 = 0;
 
 
    while (r!=0)
    {
        T temps = s2;
        s2 = s1;
        s1 = temps - s1*q;
 
        T tempt = t2;
        t2 = t1;
        t1 = tempt - t1*q;
        
        a = b;
        b = r;
        q = (a / b);
        r = a%b;
    }
    return pair<T, T>(s1, t1);
}
 
 
 
int main()
{
    int a = 69;
    int b = 23;
    pair<int, int> sol = ExtendedEuclid(a,b);
    cout << sol.first << "*" << a << "+" << b << "*" << sol.second << "=" << LoopEuclid(a, b) << endl;
    a = 67;
    b = 23;
    sol = ExtendedEuclid(a, b);
    cout << sol.first << "*" << a << "+" << b << "*" << sol.second << "=" << LoopEuclid(a, b) << endl;
}
cs


'Study > Algorithms' 카테고리의 다른 글

[Algorithm] 오일러 파이(피) 함수 Euler's phi function  (0) 2017.08.31
[Algorithm] 중국인의 나머지 정리 Chinese remainder theorem  (0) 2017.08.31
[Algorithm] Convex Hull Algorithm  (0) 2017.08.24
[Algorithm] CCW Algorithm [펌]  (0) 2017.08.24

https://en.wikipedia.org/wiki/Graham_scan


Convex Hull 알고리즘은 한국말로 볼록 껍질 알고리즘이라고도 하며


여러 점 가운데서 가장 큰 볼록 다각형을 찾는 알고리즘이다.


Graham scan(+CCW) method 를 쓴다.


https://www.acmicpc.net/problem/1708


위의 문제를 풀어보면 좋을 것 같다.

'Study > Algorithms' 카테고리의 다른 글

[Algorithm] 오일러 파이(피) 함수 Euler's phi function  (0) 2017.08.31
[Algorithm] 중국인의 나머지 정리 Chinese remainder theorem  (0) 2017.08.31
[Algorithm] 확장 유클리드 알고리즘 Extended Euclid Algorithm  (0) 2017.08.31
[Algorithm] CCW Algorithm [펌]  (0) 2017.08.24

+ Recent posts

티스토리툴바