[ 백준 ] 2824 / 최대공약수
# Appreciation
/*
* Problem :: 2824 / 최대공약수
*
* Kind :: Math
*
* Insight
* - A = a1 * a2 * ... * an
* B = b1 * b2 * ... * bm
* + g11 = gcd(a1, b1)
* g12 = gcd(a1, b2)
* ... 라고 한다면
* gcd(A,B) = gcd(a1 * a2 * ... * an, b1 * b2 * ... * bm)
* = gcd(a1, b1 * b2 * ... * bm)
* * gcd(a2, b1/g11 * b2/g12 * ... * bm/g1m)
* * gcd(a3, b1/g11/g21 * b2/g12/g22 * ... * bm/g2m)
* ...
* # gcd(a1, b1 * b2 * ... * bm)
* -> gcd(a1, b1 * b2 * ... * bm)
* = g11 * gcd(a1/g11, b2 * b3 * ... * bm)
* b1 /= g11
* = g11 * g12 * gcd(a1/g11/g12, b3 * b4 * ... * bm)
* b2 /= g12
* ...
* => gxy = gcd(ax, by)
* ans *= gxy
* ax /= gxy
* by /= gxy
*
* - 다음과 같은 입력이 들어왔다고 하자
* 2
* 20 15
* 2
* 10 10
* + A = 300 = 20 * 15
* B = 100 = 10 * 10
* # gcd(300, 100) = gcd(20 * 15, 10 * 10)
* -> ans = 1
* 20 15
* 10 10
*
* -> ans = 10 <= gcd(20, 10) / g11
* 2 15
* 1 10
*
* -> ans = 20 <= gcd(2, 10) / g12
* 1 15
* 1 5
*
* -> ans = 20 <= gcd(15, 1) / g21
* 1 15
* 1 5
*
* -> ans = 100 <= gcd(15, 5) / g22
* 1 3
* 1 1
*
* Point
* - 최대공약수는
* #include <numeric> 에 있는
* gcd(A, B) 를 통해 쉽게 구할 수 있다!
*
* - ans 를 9 자리까지만 구하면 되기 때문에
* ans %= 10^9 로 구하지만
* 만약 ans 가 10^9 보다 크지만 (9자리보다 길지만)
* 답을 출력할 때 그 순간 ans 가 10^9 보다 작다면 (8자리 이하라면)
* 9자리가 되도록 0 을 앞에 출력해주어야 한다
* + 코드의 경우 (bool) isBig 변수를 활용하여 이를 확인했으며
* printf 를 활용하였다
* # cout 에서는 setfill 을 활용해서 출력할 수도 있더라~
*/
# Code
//
// BOJ
// ver.C++
//
// Created by GGlifer
//
// Open Source
#include <iostream>
#include <numeric>
// #include <iomanip>
using namespace std;
#define endl '\n'
// Set up : Global Variables
/* None */
// Set up : Functions Declaration
/* None */
int main()
{
// Set up : I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Set up : Input
int N; cin >> N;
long A[N];
for (int i=0; i<N; i++)
cin >> A[i];
int M; cin >> M;
long B[M];
for (int i=0; i<M; i++)
cin >> B[i];
// Process
long ans = 1; /* 최대공약수 */
bool isBig = false; /* ans 가 9자리 이상인지 확인 */
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
long gij = gcd(A[i], B[j]);
ans *= gij;
if (ans >= 1'000'000'000) { /* ans 가 9자리보다 길다면 */
isBig = true; /* isBig 변수로 이를 체크 */
ans %= 1'000'000'000; /* 10^9 로 나눈 나머지로 ans 를 갱신 */
}
A[i] /= gij;
B[j] /= gij;
}
}
// Control : Output
if (isBig)
printf("%09ld\n", ans);
// cout << setfill('0') << setw(9) << ans << endl;
else
cout << ans << endl;
}
// Helper Functions
/* None */
Author And Source
이 문제에 관하여([ 백준 ] 2824 / 최대공약수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@gglifer/백준-2824-최대공약수
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
/*
* Problem :: 2824 / 최대공약수
*
* Kind :: Math
*
* Insight
* - A = a1 * a2 * ... * an
* B = b1 * b2 * ... * bm
* + g11 = gcd(a1, b1)
* g12 = gcd(a1, b2)
* ... 라고 한다면
* gcd(A,B) = gcd(a1 * a2 * ... * an, b1 * b2 * ... * bm)
* = gcd(a1, b1 * b2 * ... * bm)
* * gcd(a2, b1/g11 * b2/g12 * ... * bm/g1m)
* * gcd(a3, b1/g11/g21 * b2/g12/g22 * ... * bm/g2m)
* ...
* # gcd(a1, b1 * b2 * ... * bm)
* -> gcd(a1, b1 * b2 * ... * bm)
* = g11 * gcd(a1/g11, b2 * b3 * ... * bm)
* b1 /= g11
* = g11 * g12 * gcd(a1/g11/g12, b3 * b4 * ... * bm)
* b2 /= g12
* ...
* => gxy = gcd(ax, by)
* ans *= gxy
* ax /= gxy
* by /= gxy
*
* - 다음과 같은 입력이 들어왔다고 하자
* 2
* 20 15
* 2
* 10 10
* + A = 300 = 20 * 15
* B = 100 = 10 * 10
* # gcd(300, 100) = gcd(20 * 15, 10 * 10)
* -> ans = 1
* 20 15
* 10 10
*
* -> ans = 10 <= gcd(20, 10) / g11
* 2 15
* 1 10
*
* -> ans = 20 <= gcd(2, 10) / g12
* 1 15
* 1 5
*
* -> ans = 20 <= gcd(15, 1) / g21
* 1 15
* 1 5
*
* -> ans = 100 <= gcd(15, 5) / g22
* 1 3
* 1 1
*
* Point
* - 최대공약수는
* #include <numeric> 에 있는
* gcd(A, B) 를 통해 쉽게 구할 수 있다!
*
* - ans 를 9 자리까지만 구하면 되기 때문에
* ans %= 10^9 로 구하지만
* 만약 ans 가 10^9 보다 크지만 (9자리보다 길지만)
* 답을 출력할 때 그 순간 ans 가 10^9 보다 작다면 (8자리 이하라면)
* 9자리가 되도록 0 을 앞에 출력해주어야 한다
* + 코드의 경우 (bool) isBig 변수를 활용하여 이를 확인했으며
* printf 를 활용하였다
* # cout 에서는 setfill 을 활용해서 출력할 수도 있더라~
*/
//
// BOJ
// ver.C++
//
// Created by GGlifer
//
// Open Source
#include <iostream>
#include <numeric>
// #include <iomanip>
using namespace std;
#define endl '\n'
// Set up : Global Variables
/* None */
// Set up : Functions Declaration
/* None */
int main()
{
// Set up : I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Set up : Input
int N; cin >> N;
long A[N];
for (int i=0; i<N; i++)
cin >> A[i];
int M; cin >> M;
long B[M];
for (int i=0; i<M; i++)
cin >> B[i];
// Process
long ans = 1; /* 최대공약수 */
bool isBig = false; /* ans 가 9자리 이상인지 확인 */
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
long gij = gcd(A[i], B[j]);
ans *= gij;
if (ans >= 1'000'000'000) { /* ans 가 9자리보다 길다면 */
isBig = true; /* isBig 변수로 이를 체크 */
ans %= 1'000'000'000; /* 10^9 로 나눈 나머지로 ans 를 갱신 */
}
A[i] /= gij;
B[j] /= gij;
}
}
// Control : Output
if (isBig)
printf("%09ld\n", ans);
// cout << setfill('0') << setw(9) << ans << endl;
else
cout << ans << endl;
}
// Helper Functions
/* None */
Author And Source
이 문제에 관하여([ 백준 ] 2824 / 최대공약수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gglifer/백준-2824-최대공약수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)