BOJ : https://www.acmicpc.net/problem/9613

 

9613번: GCD 합

문제 양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1000000을 넘지 않는다. 출력 각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다. 예제 입

www.acmicpc.net

 

전체를 탐색하며 쌍을 만들고 최대공약수를 계속 더해주면 된다.

* long long 을 필수사용하자!

 

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
#include <iostream>
using namespace std;
 
int arr[100];
 
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
 
int main() {
    int T, n;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> arr[i];
 
        long long total = 0;
        for (int i = 0; i < n-1; i++) {
            for (int k = i + 1; k < n; k++) {
                if (arr[i] >= arr[k]) total += gcd(arr[i], arr[k]);
                else total += gcd(arr[k], arr[i]);
            }
        }
        cout << total << endl;
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2745번 진법 변환  (0) 2020.01.13
BOJ 11005번 진법 변환2  (0) 2020.01.13
BOJ 1850번 최대공약수  (0) 2020.01.12
BOJ 1934번 최소공배수  (0) 2020.01.12
BOJ 2609번 - 유클리드 호제법  (0) 2020.01.12

BOJ : https://www.acmicpc.net/problem/1850

 

1850번: 최대공약수

모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다.

www.acmicpc.net

 

막상 보면 당황할수도 있는 문제이다.

이럴때는 문제를 다시 천천히 읽어보자

1로만 이루어지는 수가 주어지기 때문에 결국 두 수의 최대공약수 크기만큼 1을 출력해주면 된다!

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
 
long long gcd(long long a, long long b) {
    return b ? gcd(b, a % b) : a;
}
 
int main() {
    long long a, b, c;
    cin >> a >> b;
 
    c =  a >= b ? gcd(a, b) : gcd(b, a);
    for (long long i = 0; i < c; i++) cout << 1;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 11005번 진법 변환2  (0) 2020.01.13
BOJ 9613번 GCD 합  (0) 2020.01.12
BOJ 1934번 최소공배수  (0) 2020.01.12
BOJ 2609번 - 유클리드 호제법  (0) 2020.01.12
BOJ 10430번 나머지  (0) 2020.01.12

BOJ : https://www.acmicpc.net/problem/1934

 

1934번: 최소공배수

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다. 두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

 

유클리드호제법을 이용하여 간단하게 해결할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
 
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
 
int main() {
    int T, a, b, c;
    cin >> T;
    while (T--) {
        cin >> a >> b;
        c = a >= b ? gcd(a, b) : gcd(b, a);
        cout << a / c * b / c * c << '\n';
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 9613번 GCD 합  (0) 2020.01.12
BOJ 1850번 최대공약수  (0) 2020.01.12
BOJ 2609번 - 유클리드 호제법  (0) 2020.01.12
BOJ 10430번 나머지  (0) 2020.01.12
BOJ 1168번 요세푸스 문제2  (0) 2020.01.12

BOJ : https://www.acmicpc.net/problem/2609

 

2609번: 최대공약수와 최소공배수

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를,둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

www.acmicpc.net

 

최대공약수와 최소공배수를 계산하기 전 좀더 쉽게 접근하는 방법을 소개하려고 한다.

호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b),

a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여

나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

이 호제법을 이용하면 최대공약수와 최소공배수를 쉽게 구할 수 있다.

* 최소공배수는 두 수를 각각 최대공약수로 나눈 값 * 최대공약수 가 된다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
 
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
 
int main() {
    int a, b, c;
    cin >> a >> b;
    if (a >= b) c = gcd(a, b);
    else c = gcd(b, a);
    cout << c << endl;
    cout << (a / c) * (b / c) * c;
    return 0;
}

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1850번 최대공약수  (0) 2020.01.12
BOJ 1934번 최소공배수  (0) 2020.01.12
BOJ 10430번 나머지  (0) 2020.01.12
BOJ 1168번 요세푸스 문제2  (0) 2020.01.12
BOJ 1158번 요세푸스 문제  (0) 2020.01.12

+ Recent posts

티스토리툴바