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

약수를 세는 것보다 배수를 세는 것이 더 쉽다(홀수인 약수의 합, 유일한 소인수의 개수를 구하는 방법)

SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 어떤 정수 x의 약수 중 홀수인 약수의 합을 f(x)라고 할때, L,R이 주어지면 L이상 R이하의 모든 x에 대해 f(x)의 합을 구하는 문제 단순한 방법으로는 소인수분해를 해서 홀수인 소인수들의 곱으로 약수의 합을 구하면 된다. https://deepdata.tistory.com/588 약수의 합과 약수의 개수 공식 익히기 1. 약수의 개수 자연수 n의 소인수분해가 n=px11px22...pxkk라고 한다면, n의 양의 약수의 개수는 $$d(n) = (x_{1}+1)(x_..

  • format_list_bulleted 정수론
  • · 2024. 4. 11.
  • textsms

포함 배제의 원리를 이용해 매우 큰 범위에서 조건에 맞는 수들만 빠르게 찾는 법 배우기 (+ 부분집합 구하기 재활)

1. 문제 9359번: 서로소 (acmicpc.net) 9359번: 서로소 첫째 줄에 테스트 케이스의 개수 T (0 < T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, A, B, N이 주어진다. (1 ≤ A ≤ B ≤ 1015, 1 ≤ N ≤ 109) www.acmicpc.net 2. 풀이 1015이내에서 N=109과 서로소인 수를 1초안에 찾으라고 한다면.. 보통의 방법으로는 찾기 힘들다 심지어 쿼리로 주어지니 더 어렵다 먼저 약수를 찾는 것보다 배수를 찾는 것이 쉽다는 것을 이해한다. N의 소인수를 모두 찾고, N의 소인수의 배수는 N과 서로소가 아니므로, 이 방법을 이용해 서로소가 아닌 수들을 찾는다. 범위 내에서 N과 서로소인 수와 서로소가 아닌 수로..

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

팩토리얼을 계산하지 않고도 소인수분해하는 기본기

1. 문제 15996번: 팩토리얼 나누기 (acmicpc.net) 15996번: 팩토리얼 나누기 음이 아닌 정수 N와 소수(prime number) A가 주어지면, N!을 Ak로 나누었을 때, 나머지가 0이 되는 최대의 음이 아닌 정수 k를 구하여라. (단, N!=N×(N-1)×···×1, 0!=1) www.acmicpc.net 2. 풀이 n의 범위가 231=2147483648까지로 이것의 팩토리얼을 계산하면... 상상하기도 힘든 숫자가 나올거는 뻔하니 계산하지 않고 Ak로 나눠보라는 말일텐데 어떻게 가능할까 예를 들어 생각하면 생각보다 간단한 문제다 5! = 5*4*3*2*1인데 2k로 나눈 나머지가 0이 되는 최대의 k는 어떻게 찾을까 만약 k = 0이면 당연히 5!은 ..

  • format_list_bulleted 정수론
  • · 2023. 6. 24.
  • textsms

자연수를 더해서 최소공배수를 최소로 만들기

1. 문제 11414번: LCM (acmicpc.net) 11414번: LCM 두 자연수 A, B가 주어졌을 때, A + N과 B + N의 최소공배수가 최소가 되는 자연수 N을 구하시오. www.acmicpc.net 2. 풀이 임의의 정수 k에 대하여 gcd(a,b)=gcd(a+kb,b)를 이용하자. 그러면, gcd(a+n,b+n)=gcd(a−b,b+n)=gcd(a+n,b−a)를 얻는다. 그래서 a < b이면, a+n≤gcd(a+n,b+n)≤b−a 최대공약수로 gcd(a+n,b+n) = gcd(a-b,b+n) = gcd(b-a,b+n) = b-a라고 한다면... (gcd(a,b) = gcd(abs(a),abs(b))이기 때문) b+n이 b-a의 배수라는..

  • format_list_bulleted 정수론
  • · 2023. 6. 17.
  • textsms
1부터 n까지 모든 자연수들 각각의 약수의 누적합을 구하는 방법들(double counting, harmonic lemma, dynamic programming)

1부터 n까지 모든 자연수들 각각의 약수의 누적합을 구하는 방법들(double counting, harmonic lemma, dynamic programming)

1. 문제 2247번: 실질적 약수 (acmicpc.net) 2247번: 실질적 약수 첫째 줄에 CSOD(n)을 1,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1부터 n까지 각각 약수들 중 1과 자기 자신을 제외한 약수들의 합들의 누적합을 구하는 문제 2. 방법1 가장 쉬운 방법은 1부터 n까지 순회해서 각 자연수를 i라고 한 다음, i에 대한 모든 약수를 구해서 1과 자기 자신을 제외하고 더하면 된다 약수는 O(√n) 알고리즘으로 모두 나눠보는 방식으로 구한다 그런데 p = 1부터 시작하면, i를 1로 나누면 1과 i를 더하게 되는데 실질적 약수라면 1과 i를 제외한 나머지들의 합을 구해야하니 p = 2부터 시작하는게 핵심 n = int(input()) ans..

  • format_list_bulleted 정수론
  • · 2023. 6. 15.
  • textsms