https://m.blog.naver.com/PostView.nhn?blogId=thqkdrhks22&logNo=150130493315&proxyReferer=https%3A%2F%2Fwww.google.co.kr%2F


https://nuriwiki.net/wiki/index.php/%EC%98%A4%EC%9D%BC%EB%9F%AC_%ED%94%BC_%ED%95%A8%EC%88%98



오일러 피 함수

누리위키, 온 누리의 백과사전

오일러 피 함수(Euler's phi function) 또는 오일러 파이 함수 ϕ(n)이란 어떤 자연수 n보다 작거나 같은 자연수 중에서 n과 서로소인 것의 개수를 나타내는 함수이다. 예를 들어, ϕ(8)=∣{1,3,5,7}∣=4이다. 이것을 수식으로 표현하면 다음과 같다: 

ϕ(n)=∣{a∈N|1≤a≤n,(a,n)=1}∣.

성질[편집]

p는 소수라고 하자.

  • ϕ(p)=p−1.
    • 역으로, ϕ(n)=n−1이라면, n은 소수이다.
  • ϕ(pa)=pa−pa−1.
  • (m,n)=1이라면, ϕ(mn)=ϕ(m)ϕ(n)이다. (오일러 피 함수는 곱셈적 함수이다.)




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

[Algorithm] 중국인의 나머지 정리 Chinese remainder theorem  (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

중국인의 나머지 정리는, 어떤 수 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

퍼온곳: https://www.acmicpc.net/blog/view/27


Counter Clock Wise


세 점 P1(x1, y1), P2(x2, y2), P3(x3, y3)가 있을 떄, 점 3개를 이은 선분은 어떤 방향성을 나타내게 될까요? 11758번 문제: CCW

가능한 경우의 수는 총 3가지가 있습니다. 반시계 방향, 시계 방향, 일직선. 시계 방향을 -1, 일직선을 0, 반시계 방향을 1이라고 했을 때, P1은 검정색, P2는 초록색, P3을 파란색으로 나타내면 아래 그림과 같습니다.

세 점으로 이루어진 삼각형의 면적을 구하는 방법을 이용해서 방향성을 구할 수 있습니다. S를 점 P1, P2, P3로 이루어진 삼각형의 면적이라고 했을 때

2×S=|x1y11x2y21x3y31|=(x2−x1)(y3−y1)−(y2−y1)(x3−x1)

입니다.

여기서 S의 부호에 따라서, 다음과 같이 세 가지로 나눌 수 있습니다.

  • S > 0: 반시계 방향
  • S = 0: 일직선
  • S < 0: 시계 방향

코드로 나타내면 아래와 같습니다.

int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
    int temp = x1*y2+x2*y3+x3*y1;
    temp = temp - y1*x2-y2*x3-y3*x1;
    if (temp > 0) {
        return 1;
    } else if (temp < 0) {
        return -1;
    } else {
        return 0;
    }
}



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



'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] Convex Hull Algorithm  (0) 2017.08.24

+ Recent posts

티스토리툴바