μΌ | μ | ν | μ | λͺ© | κΈ | ν |
---|---|---|---|---|---|---|
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 |
- μμꡬνκΈ°
- λ€μ΄λλ―Ήνλ‘κ·Έλλ°
- λ°±μ€
- ꡬν
- κΉμ΄μ°μ νμ
- μμνμ
- λλΉμ°μ νμ
- μν
- DFS
- μκ³ λ¦¬μ¦
- BFS
- κ·Έλννμ
- λ³ν©μ λ ¬
- db
- Side Menu
- λ°μ΄ν°λ² μ΄μ€
- 그리λ
- νλ‘κ·Έλλ¨Έμ€
- μ λ ¬
- 11650
- κ·Έλν
- νλ‘μ΄λμμ¬
- μ°μ μμν
- κ·Έλνμνλ¬Έμ
- μλ£κ΅¬μ‘°
- LIS
- DP
- λμ κ³νλ²
- λ¨Έμ§μνΈ
- SQL
πππ°πΈ π£πΆπ΅ π΄π΅π¦π’π₯πΊ
[λ°±μ€] 2609λ²: μ΅λ곡μ½μμ μ΅μ곡배μ - C++ λ³Έλ¬Έ
[λ°±μ€] 2609λ²: μ΅λ곡μ½μμ μ΅μ곡배μ - C++
.23 2021. 8. 15. 04:12λ¬Έμ
λ κ°μ μμ°μλ₯Ό μ λ ₯λ°μ μ΅λ 곡μ½μμ μ΅μ 곡배μλ₯Ό μΆλ ₯νλ νλ‘κ·Έλ¨μ μμ±νμμ€.
μ λ ₯
첫째 μ€μλ λ κ°μ μμ°μκ° μ£Όμ΄μ§λ€. μ΄ λμ 10,000μ΄νμ μμ°μμ΄λ©° μ¬μ΄μ ν μΉΈμ κ³΅λ°±μ΄ μ£Όμ΄μ§λ€.
μΆλ ₯
첫째 μ€μλ μ λ ₯μΌλ‘ μ£Όμ΄μ§ λ μμ μ΅λ곡μ½μλ₯Ό, λμ§Έ μ€μλ μ λ ₯μΌλ‘ μ£Όμ΄μ§ λ μμ μ΅μ 곡배μλ₯Ό μΆλ ₯νλ€.
μ ν΄λ¦¬λ νΈμ λ²μ μ΄μ©νμ¬ νΈλ λ¬Έμ μ΄λ€.
μ ν΄λ¦¬λ νΈμ λ²μ 2κ°μ μμ°μμ μ΅λ곡μ½μλ₯Ό ꡬνλ μκ³ λ¦¬μ¦μ νλμ΄λ€.
a > b μΈ λ μκ° μμ λ, aλ₯Ό bλ‘ λλ λλ¨Έμ§κ° rμΌλ, aμ bμ μ΅λ곡μ½μλ bμ rμ μ΅λ곡μ½μμ κ°λ€. κ°μ μλ¦¬λ‘ κ³μ κ°μ ꡬνμ¬ λλ¨Έμ§κ° 0μ΄ λμ λμ λλλ μκ° aμ bμ μ΅λ곡μ½μκ° λλ€.
μλ₯Ό λ€μ΄ 414μ 72μ μ΅λ곡μ½μλ₯Ό ꡬνμλ©΄,
414 = 72 * 5 + 54
72 = 54 * 1 + 18
54 = 18 * 3 + 0
λ°λΌμ 414μ 72μ μ΅λ곡μ½μλ 18μ΄ λλ€.
μ΅μ곡배μλ aμ bλ₯Ό κ³±ν κ°μ aμ bμ μ΅λ곡μ½μλ₯Ό λλ κ°κ³Ό κ°λ€. λ°λΌμ μμ μ±μ§λ€μ μ΄μ©νμ¬ μ΅λ곡μ½μμ μ΅μ곡배μλ₯Ό ꡬνλ ν¨μλ₯Ό μμ±νλ©΄ λ€μκ³Ό κ°λ€.
int GCD(int a, int b) {
return b ? GCD(b, a % b) : a;
}
int LCM(int a, int b) {
return a * b / GCD(a, b);
}
μ 체 μ½λλ λ€μκ³Ό κ°λ€.
μ½λ
#include <cstdio>
int GCD(int a, int b);
int LCM(int a, int b);
int main(void) {
int a, b;
scanf("%d %d", &a, &b);
printf("%d\n", GCD(a, b));
printf("%d\n", LCM(a, b));
return 0;
}
int GCD(int a, int b) {
return b ? GCD(b, a % b) : a;
}
int LCM(int a, int b) {
return a * b / GCD(a, b);
}
'μ½λ©ν μ€νΈ μ€λΉ > λ°±μ€' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[λ°±μ€] 1978λ²: μμ μ°ΎκΈ° - C++ (0) | 2021.08.17 |
---|---|
[λ°±μ€] 1934λ²: μ΅μ곡배μ - C++ (0) | 2021.08.16 |
[λ°±μ€] 11004λ²: Kλ²μ§Έ μ - C++ (0) | 2021.08.14 |
[λ°±μ€] 11652λ²: μΉ΄λ - C++ (0) | 2021.08.13 |
[λ°±μ€] 10989λ²: μ μ λ ¬νκΈ° 3 - C++ (0) | 2021.08.12 |