어려운 문제는 아니지만


auto 를 처음 써봤다. 신기하군


C++ 11 버전부터 사용 가능한 기능이라네요.


나머지 코드는 그렇게 어렵지 않습니다.


vector와 sort()




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int main(){
    int n, x, y;
    vector<pair<int, int>> v;
    
    scanf("%d", &n);
    while(n--){
        scanf("%d %d", &x, &y);
        v.push_back(make_pair(x, y));
    }
    sort(v.begin(), v.end());
    
    for(auto lt : v){
        printf("%d %d\n", lt.first, lt.second);
    }
    
    return 0;
}
 
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[4355번] 서로소 - 오일러 파이 함수[C++]  (0) 2017.08.31
[11758번] CCW - CCW 알고리즘[C++]  (0) 2017.08.24
[1463번] 1로 만들기 - 동적계획법 [C++]  (0) 2017.05.11
[1780번] 종이의 개수 - 분할정복법 [C++]  (1) 2017.05.11
[1065번] 한수 - Bruth force & Search[C++]  (0) 2017.03.27

http://min92.tistory.com/70


오일러 파이 함수를 통해서 풀면

파이는 1~n까지의 수 중에서 n과 서로소인 수의 갯수이다.




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
#include <cstdio>
#include <iostream>
#include <math.h>
 
using namespace std;
 
int prime[50];
int primeCopy[50];
 
int primeCopy2[50];
int primeCopyPower[50];
 
void function(int firstInputNumber)
{
    int i, primeIndex, inputNumber;
    int x;
    primeIndex = 0;
    inputNumber = firstInputNumber;
    
    //소인수분해
    for(i = 2; i < inputNumber; i++)
    {
        if(inputNumber % i == 0)
        {
            prime[primeIndex] = i;
            primeIndex++;
            inputNumber /= i;
            i = 1;
        }
    }
    
    x = inputNumber;
    
    i = 0;
    
    while(firstInputNumber != x)
    {
        x = x * prime[i];
        i++;
    }
    prime[i] = inputNumber;
    
    //primeCopy에는 소인수분해해서 최소공배수들이 모임
    for(int j = 0; j <= i; j++){
        primeCopy[j] = prime[j];
    }
    
    //primeCopy2에는 소인수분해해서 최소공배수가 중복되지 않게 넣음
    //primeCopyPower에는 각자의 최소공배수가 몇 개씩 있는지를 넣음
    int k = 0;
    for(int j = 0; primeCopy[j] != 0; j++){
        if(j != 0){
            if(primeCopy[j] == primeCopy[j-1]){
                primeCopyPower[k]++;
            }else{
                k++;
                primeCopyPower[k]++;
                primeCopy2[k] = primeCopy[j];
            }
        }
        else{
            primeCopyPower[k]++;
            primeCopy2[k] = primeCopy[j];
        }
    }
}
 
int main(){
    int N;
    int result = 1;
    
    while(1){
        cin >> N;
        if(N == 0) break;
        
        //initialization
        for(int k = 0; k < 50; k++){
            prime[k] = 0;
            primeCopy[k] = 0;
            primeCopy2[k] = 0;
            primeCopyPower[k] = 0;
            result = 1;
        }
        
        function(N);
        
        //오일러의 파이 함수 정리
        for(int j = 0; primeCopy2[j] != 0; j++){
            result *= pow(primeCopy2[j], primeCopyPower[j]) - pow(primeCopy2[j], primeCopyPower[j]-1);
        }
        printf("%d\n", result);
    }
    
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[11650번] 좌표 정렬하기 - sort [C++]  (0) 2017.09.19
[11758번] CCW - CCW 알고리즘[C++]  (0) 2017.08.24
[1463번] 1로 만들기 - 동적계획법 [C++]  (0) 2017.05.11
[1780번] 종이의 개수 - 분할정복법 [C++]  (1) 2017.05.11
[1065번] 한수 - Bruth force & Search[C++]  (0) 2017.03.27

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

+ Recent posts

티스토리툴바