넘치게 채우기

https://www.acmicpc.net/problem/27172BOJ - 수 나누기 게임문제 유형: 수학, 정수론문제 난이도: Gold IV시간 제한: 1초메모리 제한: 1024MB 문제《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다.《수 나누기 게임》의 규칙은 다음과 같습니다.게임을 시작하기 전 각 플레이어는 1$1$부터 1000000$1\,000\,000$ 사이의 수가 적힌 서로 다른 카드를 잘 섞은 뒤 한 장씩 나눠 가집니다.매 턴마다 플레이어는 다른 플레이어와 한 번씩 결투를 합니다.결투는 서로의 카드를 보여주는 방식으로 진행되며, 플레이어의 카드에 적힌 수로 다른 플레이어의 카드에 적힌 수를 나눴을 때, 나머지..

https://www.acmicpc.net/problem/1644BOJ - 소수의 연속합문제 유형: 수학, 정수론, 슬라이딩 윈도우문제 난이도: Gold III시간 제한: 2초메모리 제한: 128MB 문제하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.3 : 3 (한 가지)41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)53 : 5+7+11+13+17 = 53 (두 가지)하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+..

https://codeforces.com/contest/2043/problem/BEducational Codeforces Round 173(Div.2) - B. Digits문제 유형: 수학, 정수론시간 제한: 1초메모리 제한: 256MB 문제Artem wrote the digit d">d on the board exactly n!">n! times in a row. So, he got the number dddddd…ddd">dddddd…ddd (exactly n!">n!digits).Now he is curious about which odd digits from 1">1to 9">9 divide the number written on the board. Artem은 정수 d를 정확히 n!..

https://www.acmicpc.net/problem/31288BOJ - 캬루문제 유형: 수학, 애드 혹, 해 구성하기, 정수론문제 난이도: Silver II시간 제한: 1초메모리 제한: 1024MB 문제이번에 캬루는 소수를 배신했다. 소수의 한 자리를 바꾸어서 소수가 아니게 만들어버렸다. 구체적으로는, 0으로 시작하지 않는 N자리 소수 P에 대해 어떤 수 Q가 P-캬루라는 것은 다음을 모두 만족하는 것을 의미한다. Q는 2 이상의 N자리 정수이며, 0으로 시작하지 않는다. P와 Q의 서로 다른 자릿수는 하나뿐이다. Q는 소수가 아니다.다음은 N=2,P=19일 때 P-캬루와 P-캬루가 아닌 수의 예시이다. Q=9는 1자리 정수이므로 19-캬루가 아니다. 09처럼 수가 0으로 시작할 수는 없다. Q=9..

https://www.acmicpc.net/problem/1124BOJ - 언더프라임문제 유형: 수학문제 난이도: Silver I시간 제한: 2초메모리 제한: 128MB 문제자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다.어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면, 그 수를 언더프라임 이라고 한다. 12는 목록에 포함된 소수의 개수가 3개이고, 3은 소수이니 12는 언더프라임이다.두 정수 A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 정수 중에서 언더프라임인 것의 개수를 구해보자. 입력첫째 줄에 두 정수 A와 B가 주어진다. 2  출력첫째 줄에 A보다 크거나 같고, B보..

https://www.acmicpc.net/problem/13172BOJ - Σ문제 유형: 정수론, 분할 정복문제 난이도: Gold IV시간 제한: 1초메모리 제한: 512MB 문제실제로 존재하는지 아닌지는 차치하고, 당신에게 삼면체 주사위가 있어서 이 주사위를 굴린다고 생각해보자. 주사위를 굴렸을 때 각 면이 나올 확률은 모두 동일하게 1/3 이다. 한 면에는 1, 다른 한 면에는 2, 남은 한 면에는 4가 적혀있다고 하면 주사위를 굴렸을 때 나오게 되는 숫자의 기댓값은 과연 몇일까? 간단하게도 셋의 평균인 7/3이 될 것이다.이 문제를 조금 확장해서, "N면체 주사위의 각 면에 적힌 수가 주어졌을 때, 주사위를 굴렸을 때 각 면이 나올 확률이 모두 같다면 주사위를 굴렸을 때 나오게 되는 수의 기댓값은..

https://leetcode.com/problems/prime-subtraction-operation/description/?envType=daily-question&envId=2024-11-11leetcode - Prime Subtraction Operation문제 유형: 정수론, 수학, 그리디문제 난이도: Medium 문제You are given a 0-indexed integer array nums of length n.You can perform the following operation as many times as you want:Pick an index i that you haven’t picked before, and pick a prime p strictly less than nums[..

https://www.acmicpc.net/problem/25342BOJ - 최대 최소공배수문제 유형: 정수론, 수학, 그리디문제 난이도 : Gold III 제한시간: 1초메모리: 1024MB 문제 1부터 N까지의 수가 있다. 최소공배수가 최대가 되도록 서로 다른 3개의 수를 선택해 보자. 입력첫째 줄에 테스트케이스의 개수 T가 주어진다. (1≤T≤1000)둘째 줄부터 T개의 줄에 각각 자연수 N$N$이 주어진다. (3≤N≤100000) 출력각 테스트케이스마다, 최소공배수의 최댓값을 한 줄에 하나씩 차례대로 출력한다. 풀이중점은 세 수의 곱을 최대화하면서 gcd의 크기를 작게 하도록 하는 것이다.n이 홀수인 경우, lcm(n, n-1, n-2)가 가장 크다고 할 수 있다.n과 n-2가 홀수가 되어 gcd..

https://leetcode.com/problems/fraction-addition-and-subtraction/description/?envType=daily-question&envId=2024-08-23leetcode - Fraction Addition and Subtraction문제 유형 : 문자열 처리, 수학, 정수론문제 난이도 : Medium 문제Given a string expression representing an expression of fraction addition and subtraction, return the calculation result in string format irreducible fraction. If your final result is an integer, c..

만일 m이 a-b를 나눌 때, a와 b가 모듈러 m에 대해 합동이다. 특히, a를 m으로 나눈 나머지가 r이면, a와 r는 모듈러 m에 대해 합동이다. 이떄, 나머지 r은 0 = 1이고 gcd(a, m) = g를 만족한다고 하자. 만일 g !| b이면, 합동방정식 은 해를 가지지 않는다. 만일 g | b이면, 합동방정식 정확히 g개의 서로 다른 해를 가진다. 모든 해를 찾으려면, 우선 일차방정식 au + mv = g의 해 (u0, v0)을 찾는다. x0 = cu/g가 의 해가 되고, 모든 합동이 아닌 해는 과 같이 나타낼 수 있다. 주의 선형 합동방정식 정리에서 가장 중요한 경우는 gcd(a, m) = 1인 경우이다. 이 경우, 합동방정식은 단 하나의 해를 가진다. 고차 합동방정식 고차 합동방정식도 수론..