정수의 임의의 거듭제곱들의 합을 바라보는 놀라운 방법

15319번: 동혁이의 생일선물 정수 x의 거듭제곱 $x^{0}, x^{1}, x^{2}, ...$에 대하여 이들의 모든 부분집합 A1, A2, ...을 생각하자 각 부분집합의 원소들의 합을 M1, M2,...라고 할 때 이들을 오름차순으로 정렬하면 수열 a1, a2,...를 얻는다 이때 k번째 원소 ak에 대하여 n개의 x,k가 주어질때 각각 구한 모든 ak의 합을 10^9 + 7로 나눈 나머지를 구한다 --------------------------------------------------------------------------------------------------------------------------------------------------------------- 2,3,4,....

• format_list_bulleted 정수론
• · 2025. 2. 11.
• textsms

BFS로 어떤 정수의 0과 1로만 이루어진 배수 찾기

4994번: 배수 찾기 정수 N이 주어질때, N의 배수 중에 0과 1로만 이루어진 배수 M을 찾는다 1보다 큰 M의 길이는 100이 넘지 않아야하고 가능한 경우가 여러가지 있으면 아무거나 찾는다 ---------------------------------------------------------------------------------------------------------------------------------------- 100000000000000000000000000000000 해서 0인거 하나씩 1로 바꿔보고 11000000000000000000000, 101000000000000000000.... 근데 하나만 바꾸는게 아니라 문제는 2개 이상 바꿔야할수도 있잖아 11100000000..

• format_list_bulleted DFS BFS 정복기
• · 2025. 1. 28.
• textsms

n이 매우 큰데 p가 매우 작은 경우에 효과적으로 n! mod p을 계산하는 방법

Factorial modulo p - Algorithms for Competitive Programming (cp-algorithms.com) Factorial modulo p - Algorithms for Competitive Programming Factorial modulo $p$ In some cases it is necessary to consider complex formulas modulo some prime $p$, containing factorials in both numerator and denominator, like such that you encounter in the formula for Binomial coefficients. We consider the case when c..

• format_list_bulleted 정수론
• · 2023. 8. 4.
• textsms

이항계수를 소수로 나눈 나머지 구하는 방법 - Lucas' Theorem 배우고 적용하기

https://en.wikipedia.org/wiki/Lucas%27s_theorem Lucas's theorem - Wikipedia From Wikipedia, the free encyclopedia In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient ( m n ) {\displaystyle {\tbinom {m}{n}}} by a prime number p in terms of the base p expansions of the integers m and n. en.wikipedia.org 1. Lucas' Theorem 정수 m,n과 소수 p에 대하여 $$\binom{m}{n..

• format_list_bulleted 정수론
• · 2023. 7. 4.
• textsms

정수 M으로 나누어 떨어지는 부분 구간합을 선형시간에 구하는 놀라운 방법

1. 문제 10986번: 나머지 합 (acmicpc.net) 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 2. 풀이 누적합이야 prefix sum 방법으로 O(N)에 미리 구해놓고 [i,j]의 구간합은 O(1)에 구할 수 있는데 정수 M으로 나누어 떨어지는 구간합 [i,j]를 어떻게 하면 아주 빠르게 구할 수 있을까 가장 쉬운 방법은 모든 i,j에 대해 검사하는 이중 for문 방법이지만 N이 $10^{6}$이다 보니 $O(N^{2})$으로는 1초안에 통과할 수..

• format_list_bulleted 누적 합 알고리즘
• · 2023. 6. 6.
• textsms

숫자를 안만들고 나머지를 구하는 방법, 문자열 연산 없이 두 수를 붙이는 방법

1. 문제 27965번: N결수 (acmicpc.net) 27965번: N결수 $10$진법 상에서 양의 정수 $1$, $2$, $3$, $\cdots$, $N$을 이어 붙여 만든 수 $\overline{123\cdots N}$을 $N$결수라고 한다. 예를 들어 $12345$는 $5$결수이고, $12345678910111213$은 $13$결수이다. $N$과 정수 $K$가 주어 www.acmicpc.net 2. 풀이1 쉽다는데... 솔직히 까다로운 문제같다 n이 10의 7제곱까지라 n결수를 만들면 당연히 시간초과일거고 (애초에 만들어지지도 않음) 그 전에 근본적으로 나눗셈 연산을 어떻게 하는지 생각을 해보면.. 1234를 5로 나누는 것은 어떻게 할까? 1을 5로 나눠보고.. 몫이 0이고 나머지가 1이니까 ..

• format_list_bulleted 정수론
• · 2023. 5. 8.
• textsms