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



이 문제 역시 유클리드 호제법으로 풀 수 있습니다. 

https://haula.tistory.com/entry/%E3%85%81 <- 여기서 자세한 알고리즘 설명을 확인 하실 수 있습니다.


여기서 주의할 것은 자료형입니다.

입력으로 주어지는 수는 범위가 1,000,000까지 입니다.

총 합의 범위는 10*99/2*1,000,000 이므로 49억입니다.

int형의 표현범위는 +-21억이며, unsigned int형의 표현범위는 +42억입니다.

따라서 이를 넘는 범위인 long long 형으로 선언해야합니다. (long long의 표현범위눈 +-900경입니다.)


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
#include<iostream>
 
using namespace std;
 
int gcd(int x, int y)
{
    if (x % y == 0) return y;
    else return gcd(y, x % y);
}
 
int main()
{
    int t, n;
    long long n_arr[101] = { 0 };
    long long sum[101] = { 0 };
 
    cin >> t;
 
    for (int i = 0; i < t; i++)
    {
        cin >> n;
        for (int j = 0; j < n; j++)
        {
            cin >> n_arr[j];
        }
        for (int k = 0; k < n; k++)
        {
            for (int p = k + 1; p < n; p++)
            {
                sum[i] += gcd(n_arr[k], n_arr[p]);
            }
        }
    }
 
    for (int i = 0; i < t; i++)
    {
        cout << sum[i]<<"\n";
    }
}
cs




정답확인 완료하였습니다.



저작자표시

'백준 문제풀이 (C++) > 수학' 카테고리의 다른 글

[수학] 1934번 최소공배수 C++ 풀이법  (0) 2020.08.22
[수학] 2609번 최대공약수와 최소공배수 C++ <유클리드 풀이>  (0) 2020.08.22
[수학] 10430번 나머지  (0) 2020.08.21


1934번은 앞전에 풀었던 2609번과 유사한 방법으로 풀 수 있습니다.

최소공배수를 구하기 위해서는 최대공약수를 먼저 구한다음에, 두 수를 각각 최대공약수로 나눈 나머지와 최대공약수를 곱해주면 쉽게 구할 수 있습니다.


https://haula.tistory.com/entry/%E3%85%81


알고리즘이 궁금하신분은 여기서 확인하시면 됩니다.


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
#include<iostream>
 
using namespace std;
 
int divide(int x, int y)
{
    if (x % y == 0)
        return y;
    else
        return divide(y, x % y);
}
 
int main()
{
    int T;
    int A, B;
    cin >> T;
 
    for (int i = 0; i < T; i++)
    {
        cin >> A >> B;
        if (A >= B)
        {
            cout << A * B / divide(A, B) << "\n";
        }
        else
            cout << A * B / divide(B, A) << "\n"; 
    }
}
cs



정답처리 확인하였습니다. 감사합니다. 

저작자표시

'백준 문제풀이 (C++) > 수학' 카테고리의 다른 글

[수학] 9613번 GCD 합 C++ 풀이법  (0) 2020.08.22
[수학] 2609번 최대공약수와 최소공배수 C++ <유클리드 풀이>  (0) 2020.08.22
[수학] 10430번 나머지  (0) 2020.08.21


이 문제는 최소공배수와 최대공약수를 구하는 문제입니다. 

최대공약수를 구한다음, 주어진 수를 최대공약수로 나눈 뒤 나머지들을 최대공약수와 곱해주면 최소공배수를 구할 수 있습니다. 

그렇다면 최대공약수는 어떻게 구하면 될까요?


유클리드 알고리즘을 이용하면 됩니다. 


유클리드 호제법(=유클리드 알고리즘) 은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나입니다.

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

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 


쉽게 설명하자면, 

1. 큰수를 작은 수로 나눕니다.

2. 나누는 수를 나머지로 계속 나눕니다. 

3. 나머지가 0이 나올 때까지 반복합니다.

4. 나머지가 0이 나온다면 그 때 나누는 수가 최대공약수가 됩니다.


예시를 들어 설명드리겠습니다.

1512와 1008의 최대공약수를 구해봅시다.

우선 1512가 1008보다 크니까 1512를 1008로 나눠줍니다. 그럼 나머지가 504가 나오죠?

그럼 1008을 504로 나눠줍니다. 그럼 나머지가 0으로 떨어지죠

그렇다면 1512와 1008의 최대공약수는 504입니다.


1. 1512%1008=504

2. 1008%504=0

그렇다면 최대공약수는 504


이번엔 1440과 864의 최대공약수를 구해볼까요?

1440을 864로 나눠줍니다. 그럼 나머지는 576이 나오죠

그리고 864를 576으로 또 나눠줍니다.

나머지가 288이 나옵니다.

576을 다시 288로 나눠줍니다. 그럼 나머지가 0이나오죠. 그러면 288이 최대공약수가 됩니다.


1. 1440%864=576

2. 864%576=288

3. 576%288=0

따라서 최대공약수는 288


이해가 되시나요?!


그렇다면 왜 이런 방법이 성립되는지 증명을 해보도록하겠습니다.


그럼 코딩으로 구현해보겠습니다.


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
#include<iostream>
 
using namespace std;
 
int divide(int x, int y)
{
    if (x % y == 0)
    {
        return y;
    }
    return divide(y, x % y);
}
 
int main()
{
    int A, B;
    int common_max = 0;
    cin >> A >> B;
 
    if (A >= B)
    {
        common_max=divide(A, B);
    }
    else common_max=divide(B, A);
 
    cout << common_max << "\n";
    cout << A * B / common_max << "\n";
}
cs




정답입니다.

저작자표시

'백준 문제풀이 (C++) > 수학' 카테고리의 다른 글

[수학] 9613번 GCD 합 C++ 풀이법  (0) 2020.08.22
[수학] 1934번 최소공배수 C++ 풀이법  (0) 2020.08.22
[수학] 10430번 나머지  (0) 2020.08.21


백준 10430번 나머지 문제풀이



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
 
using namespace std;
 
int main()
{
    int A, B, C;
    cin >> A >> B >> C;
 
    cout << (A + B) % C<<"\n";
    cout << ((A % C) + (B % C)) % C << "\n";
    cout << (A * B) % C << "\n";
    cout << ((A % C) * (B % C)) % C << "\n";
 
    return 0;
}
cs


저작자표시

'백준 문제풀이 (C++) > 수학' 카테고리의 다른 글

[수학] 9613번 GCD 합 C++ 풀이법  (0) 2020.08.22
[수학] 1934번 최소공배수 C++ 풀이법  (0) 2020.08.22
[수학] 2609번 최대공약수와 최소공배수 C++ <유클리드 풀이>  (0) 2020.08.22

+ Recent posts

티스토리툴바