모든 순서쌍의 합의 나머지를 합해야하는데 매 항마다 나머지를 더하면 안되는 문제

C - Sigma Problem (atcoder.jp) C - Sigma ProblemAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  f(x,y) = x + y를 108108로 나눈 나머지라고 정의 모든 i = 1,2,3,...,n-1, i  예를 들어 3 50000001 50000002이면... (3, 50000001), (3, 50000002), ( 50000001, 50000002)가 있고... 50000004, 50000005, (100000003 % 100000000 = 3)이 된다. 이들을 합하면 10000..

  • format_list_bulleted 애드 혹 알고리즘
  • · 2024. 6. 6.
  • textsms

n으로 나누어 떨어지면서 자릿수의 합도 n으로 나누어 떨어지는 정수

30599번: Divisibility Trick (acmicpc.net) 3의 배수 판정법은 어떤 정수의 자릿수 합이 3으로 나누어 떨어지면, 3의 배수이다. 9의 배수도 마찬가지다. 어떤 정수 n의 자릿수의 합이 d로 나누어 떨어지면서 n도 d로 나누어 떨어지는 정수 n을 아무거나 하나 찾으면 된다 생각했던 방법은 각 자릿수는 0~9까지니까 자릿수 합이 d로 나누어 떨어지게 되는 가장 작은 수는  '1'을 d개만큼 이어 붙이는 것이라고 생각했다.  x = 111111111111111111111111111.....1111111 이러면 자릿수 합이 d니까 d로 나누어 떨어진다. 이 x를 d로 나누었을 때 x = d*p + r이 될 것인데 d(p+1)부터 시작해서 d(p+2), d(p+3), ....을 모두..

  • format_list_bulleted 애드 혹 알고리즘
  • · 2024. 6. 1.
  • textsms

1부터 n까지 각각 1번씩 정확히 k개의 정수만 사용해서 합을 s로 만드는 그리디 알고리즘

19177번: Klothes (acmicpc.net) 1부터 n까지의 자연수 중에서 각각 1번씩만 사용하고, 정확히 k개의 정수만 사용해서 합을 s로 만드는 방법을 찾는 문제 n이 40000까지이고 테스트케이스가 8000개이다 보니 단순한 방법보다는 O(N)정도에 하나는 해결해야  만약 s가 가능한 범위를 벗어난다면 일단 만들수가 없다. s의 최솟값은 1부터 k까지 합 s의 최댓값은 n-k+1,n-k+2,...,n까지의 합 만약 s가 (1부터 k까지 합)   반대로 이 범위 안이라면 확실하게 만들 수 있다는 것이 보장된다. (1부터 k까지의 합) = a (n-k+1,...,n까지의 합) = b라고 할 때, a,a+1,a+2,..,b-1,b까지의 모든 정수는 반드시 만들 수 있다. 어떤 정수는 안되는게 있..

  • format_list_bulleted 그리디 알고리즘
  • · 2024. 5. 29.
  • textsms

골드바흐의 추측을 이용해 정수 n을 k개의 소수 합으로 표현하기

25309번: K개의 소수 (acmicpc.net) 정수 n을 k개의 소수 합으로 표현하라는 문제 여기서 핵심은 서로 다른 k개의 소수가 아니라, 같은 소수를 사용해도 좋다. 그리고 문제는 n이 최대 108이고 k는 최대 10000이라 단순한 방법으로는 어렵다 먼저 생각할 수 있는 것은 가장 작은 소수가 2이기 때문에, 2를 k개 사용하여 2k가 만들 수 있는 정수의 최솟값이다. 따라서 n = 2k이면 일단 분해하는 것이 가능하다. n,k = map(int,input().split())if n   만약 k = 1이면 n 자체로 소수인지 아닌지 판단하면 된다.  O(√n)에 소수 판단할 수 있다. def is_prime(n): for i in range(2,int(n**..

  • format_list_bulleted 정수론
  • · 2024. 5. 24.
  • textsms

이진수의 마지막 n개의 비트가 모두 켜져있는지 확인하는 방법

SW Expert Academy SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  정수 m의 마지막 n개의 비트가 모두 1인지 확인하는 문제 m이 108이고 테스트 케이스는 10000개이고 제한시간 2초라 단순하게 확인하면 시간초과날 것 같다 가장 쉬운 방법은 0부터 n-1까지 순회해서 각 비트가 1인지 검사하는 것 (1 이다. T = int(input())for test_case in range(1, T + 1): n,m = map(int,input().split()) no = False for i in range(n): if (1   다른..

  • format_list_bulleted 비트마스킹
  • · 2024. 5. 3.
  • 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