최대공약수
-
백준 17087 - 숨바꼭질 6백준 algorithm 2020. 3. 18. 18:27
=> 나( S )가 갈 수 있는 곳은 ( S + D ) or ( S - D ) 이다. => 내가 Y에 가기 위해서는 Y-S 의 절대값이 D의 배수가 되어야한다. => 내가 Z에 가기 위해서는 Z-S 의 절대값이 D의 배수가 되어야한다. => 모든 Y-S , Z-S 값들의 최대 공약수를 구하면 된다. ex ) S : 3 동생들 위치 : 1 7 11 이 경우 최대공약수를 구해야할 수들은 2 4 8 가 된다. *** 배열을 사용할 때 잘못된 index에 접근하거나, 0으로 나누는 경우가 없도록 주의해야한다. (런타임 에러) #include #include #include #include using namespace std; long GCD (long A, long B) { while(B!=0) { long t..
-
백준 2609 - 최대공약수와 최소공배수백준 algorithm 2020. 3. 13. 13:03
=> GCD와 LCM ( 최대공약수와 최소공배수 ) 를 구할 수 있는지에 대한 문제이다. => 함수 두개를 생성하여 만들었다. => GCD : 유클리드 호제법 LCM :gcd*(A/gcd)*(B/gcd) 이다. #include #include #include #include using namespace std; int GCD (int A, int B) { while(B!=0) { int tmp=B; B=A%B; A=tmp; } return A; } int LCD(int A, int B) { int gcd=GCD(A, B); return gcd*(A/gcd)*(B/gcd); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.ti..
-
백준 1850 - 최대공약수백준 algorithm 2020. 3. 10. 01:19
=>실제로 입력받은 갯수로 1로 이루어진 숫자로 최대 공약수를 만들면 안된다. =>입력 받은 값의 최대 공약수를 구한 다음 그 값을 limit으로 1을 출력하면 된다. #include #include #include #include #include using namespace std; int gcd(long long a, long long b) { long long c; while (b != 0) { c = a % b; a = b; b = c; } return a; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); long long A,B; cin>>A>>B; int limit=gcd(A,B); for..