바야바네 움집

📌풀이 입력된 값들의 모든 gcd 쌍을 구하면 되는 문제. 10번 정도 틀렸는데 그 이유는 자료형 문제 때문이었음. 변수 자료형 뿐만 아니라 서식지정자 또한 lld로 변경해주어야 함. 📌코드 #include long long GCD(long long D, long long B); int main(){ int testCase, count; long long valueArr[1000], sumArr[5000] = {0}; scanf("%d", &testCase); for(int i=0; i

📌코드 #include int GCD(int D, int B); int main() { int arr[1000]; int testCase, count; int a, b; scanf("%d", &testCase); count = testCase; while(testCase){ scanf("%d %d", &a, &b); arr[testCase-1] = a*b / GCD(a, b); testCase--; } for(int i=count-1; i>-1; i--) printf("%d\n", arr[i]); return 0; } int GCD(int D, int B) { int R; R = D % B; //D = B * (D/B) + R; if(R!=0) GCD(B, R); else return B; }

최대공약수와 최소공배수 구하는 법을 까먹었다. 초등학교부터 다시 다녀야할 것 같다. 📌최대공약수와 최소공배수 구하는 방법 1. 소인수분해 두 수를 소인수분해를 한다. 두 수의 공통된 소인수를 모두 곱하면 최대공약수, 두 수의 모든 소인수를 곱하면 최소공배수가 된다. 2. 유클리드 호제법 A와 B의 최대공약수를 구하기 위해서 A를 B로 나눈 나머지 R1을 구한다. B를 R1으로 나눈 나머지 R2를 구한다. R1을 R2로 나눈 나머지 R3를 구한다 이 과정을 계속 반복하여, 어느 한 쪽이 나누어떨어질 때까지 반복한다. 이 직전 얻은 나머지가 최대공약수. 예시로 1254와 582의 최대공약수를 구해보자. 1254=582×2+901254=582×2+90 582=90×6+42582=90×6+42 90=42×2+6..