어쨌든 공부하는 블로그

우선 두 수의 최소공배수(LCM)는 두 수의 곱을 최대공약수로 나눠주면 구할 수 있다따라서 최대공약수(GCD)를 구하는 것이 중요하다 a와 b의(단, a > b)최대 공약수는 a % b(mod), 즉 나머지가 0이 될 때까지 아래와 같이 반복하여 구할 수 있다1. a % b = r, 나머지의 값을 구한다2. b를 나머지(r)로 나눈 값의 나머지(r')를 구한다3. r을 r'로 나눈 값의 나머지(r'')를 구한다... 1. 재귀함수로 구현int gcd(int a, int b){ if (a % b == 0) return b; return gcd(b, a % b);} 2. 반복문으로 구현int gcd(int a, int b){ int r = a % b; while(r) ..

https://www.acmicpc.net/problem/21920풀이1x의 소인수를 저장해두고, 입력된 수들을 x의 소인수들로 나눠서 서로소인지 여부를 확인한다 제출 코드#include #include using namespace std;int arr[500001];int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, x; cin >> n; for (int i = 0; i > arr[i]; cin >> x; vector v; // x의 소인수 구하기 for (int i = 2; i  풀이2서로소라는 것은 두 수의 최대공약수가 1인 수라는 의미이다이를 그대로 해석하여 gcd ..

https://www.acmicpc.net/problem/5347풀이최소공배수(LCM)와 최대공약수(GCD)를 유클리드 호제법을 이용해 푸는 문제다 두 수의 최소 공배수는 두 수의 곱을 최대 공약수로 나누면 구할 수 있다 a와 b의(단, a > b)최대 공약수는 a % b(mod), 즉 나머지가 0이 될 때까지 아래와 같이 반복하여 구할 수 있다1. a % b = r, 나머지의 값을 구한다2. b를 나머지(r)로 나눈 값의 나머지(r')를 구한다3. r을 r'로 나눈 값의 나머지(r'')를 구한다...  제출 코드#include using namespace std;long long gcd(long long a, long long b){ if (a % b == 0) return b; ..