정수론35 [백준] 16970번 : 정수 좌표의 개수 (C++) 16970번 : 정수 좌표의 개수 문제) 2차원 좌표 평면 위에서 두 점을 골라 선분을 그었을 때, 지나가는 점의 개수가 K개인 선분의 수를 구해보자. 가능한 점의 좌표 (x, y)는 0 ≤ x ≤ N, 0 ≤ y ≤ M 이고, x와 y는 정수이다. 선분의 양 끝점도 선분이 지나가는 점이다. 입력 : 첫째 줄에 N, M, K가 주어진다. 출력 : 첫째 줄에 지나가는 점의 개수가 K개인 선분의 수를 출력한다. 풀이) 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58.. 2024. 1. 13. [백준] 10859번 : 뒤집어진 소수(C++) 10859번 : 뒤집어진 소수 문제) 어제 자다가 알람 시계를 떨어뜨렸는지, 08:15분이 51:80분이 되어 있었다. 그때 나는 디지털로 표시된 어떤 숫자는 180도 뒤집혔을 때도 숫자가 될 수 있다는 걸 깨달았다. 내가 좋아하는 숫자는 소수이다. 당신이 할 일은 주어진 숫자가 소수인지, 뒤집혀서도 소수인지 확인하는 것이다. 입력 : 첫 번째 줄에 N이 주어진다 (1 ≤ N ≤ 10^16). N의 첫 숫자는 0이 아니다. 출력 : 첫 번째 줄에 N이 소수이고 뒤집혀서도 소수이면 "yes"를 출력하고, 아니면 "no"를 출력한다. 풀이) 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 32 33 34 3.. 2024. 1. 13. [백준] 14232번 : 보석 도둑 (C++) 14232번 : 보석 도둑 문제) 희대의 도둑 효빈이는 세계 최고의 보석가게 영선상에 잠입할 계획이다. 이 영선상은 최고의 보석가게답게 최고의 보안장치를 두고 있는데, 이 보안장치를 해제하지 않는다면 보석을 여러 개 훔쳐갈 시, 보석끼리 달라붙으며 무게가 모든 보석들의 곱으로 늘어난다. 효빈이는 이 보안장치를 해제할 수 없기 때문에, 차라리 곱해진 대로 최대한 많은 보석들을 가져오기로 계획했다. 효빈이는 한번에 k라는 무게를 들 수 있으므로, 딱 k만큼의 무게만큼의 보석을 가져오고 싶은데, 그 때 보석들의 최대 개수를 알고싶다. 영선상에는 세계 최고의 보석가게답게 모든 무게의 보석들이 매우 많이때문에, 훔쳐가는 보석이 부족할 일은 없다. 다만 모든 보석들은 무게가 1보다 크다. 효빈이는 이제 영선상에 잡.. 2024. 1. 13. [백준] 1816번 : 암호키 (C++) 1816번 : 암호키 문제) 현대 사회에서 통용되고 있는 많은 종류의 암호 시스템에서는, 매우 큰 소수의 곱으로 만들어진 수를 암호 키로 이용하는 경우가 많다. 현실적으로 매우 큰 수를 빠른 시간 내에 소인수분해하는 것은 어려운 일이기 때문이다. 물론 실제 생활에서는 수십만 또는 수백만 자리 이상의 매우 큰 소수가 활용되지만 그러한 소수를 구하는 것은 매우 어려운 일이므로, 우리는 좀 더 스케일이 작은 경우에 대해서만 생각해 보기로 하자. 1,000,000=106보다 큰 소수이면 매우 큰 소수로 생각하는 것이다. 어떤 수 S가 주어지면, 이 수가 우리가 생각하는 스케일이 작은 경우에서 적절한 암호 키인지 아닌지를 구하는 프로그램을 작성하시오. 만일 S의 모든 소인수가 106보다 크다면 그 수는 적절한 암.. 2024. 1. 5. 이전 1 2 3 4 5 6 7 ··· 9 다음
