본문 바로가기

정수론35

[백준] 9613번 : GCD 합 (C++) 9613번 : GCD 합 문제) 양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오. 입력 : 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다. 출력 : 각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다. 풀이) 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 4.. 2023. 9. 3.
[백준] 22943번 : 수 (C++) 22943번 : 수 문제) 0부터 9까지 K가지의 숫자를 한 번씩만 사용하여 만들 수 있는 수 중 아래 조건을 모두 만족하는 수들의 개수를 구해보자. 단, 수의 맨 앞에는 0이 올 수 없다. 즉, 0143는 불가능하다. 서로 다른 두 개의 소수의 합으로 나타낼 수 있는 경우 M으로 나누어 떨어지지 않을때까지 나눈 수가 두 개의 소수의 곱인 경우, 이 때, 두 개의 소수가 같아도 된다. 예를 들어, K$ 1이고 M$ 11인 경우로 생각해보자. 한자리 수 중 1번 조건을 만족하는 수는 5, 7, 8, 9이고 2번 조건을 만족하는 수는 4, 6, 9가 있다. 이 두개의 조건을 둘다 만족하는 수는 9이므로 이 경우에는 1개이다. 입력 : 첫 번째 줄에 K와 M 주어진다. 출력 : 2가지 조건을 만족하는 수의 개.. 2023. 8. 23.
[백준] 21920번 : 서로소 평균 (C++) 21920번 : 서로소 평균 문제) 효성이는 길이가 N인 수열 A에서 X와 서로소인 수들을 골라 평균을 구해보려고 한다. 효성이를 도와 이를 계산해주자. 입력 : 첫 번째 줄에 입력될 수들의 개수 N이 주어진다. (2≤N≤500,000) 두 번째 줄에는 수열 A를 이루는 자연수 A_i 가 공백으로 구분되어 주어진다. (2≤a_i≤1,000,000) 수열 A에 X와 서로소인 수가 최소 1개 이상 존재한다. 마지막 줄에는 X가 주어진다. (2≤X≤1,000,000) 출력 : 첫째 줄에 수열 A에서 X와 서로소인 수들의 평균을 출력한다. 절대/상대 오차는 10-6까지 허용한다. 풀이) 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 2.. 2023. 8. 19.
[백준] 18512번 : 점프 점프 (C++) 18512번 : 점프 점프 문제) 두 학생 A와 B가 일직선상의 트랙에서 같은 방향으로 멀리뛰기를 하고 있다. A는 한 번에 X 미터를, B는 한 번에 Y 미터를 뛴다. 두 학생의 시작 지점과 X, Y에 대한 정보가 주어졌을 때, 두 학생이 공통적으로 지나게 되는 지점 중에서 시작 지점으로부터 가장 가까운 지점을 찾는 프로그램을 작성하시오. 예를 들어 한 번에 10미터를 뛰는 A는 30의 지점에서 멀리뛰기를 시작하고, 한 번에 12미터를 뛰는 B는 8의 지점에서 시작한다고 가정하자. A가 5번의 멀리뛰기를 하고, B가 6번의 멀리뛰기를 하면 두 사람은 80의 지점을 공통으로 지나게 되며, 이는 두 학생의 시작 지점에서 가장 가까운 지점이다. 입력 : 첫째 줄에 두 사람이 한 번에 멀리뛰기를 하는 거리 X.. 2023. 8. 6.

티스토리툴바