백준 13504번 XOR 합
백준 13504번 XOR 합 풀이. 누적 XOR 값을 Trie에 넣고 두 prefix XOR의 최대 조합을 찾아 부분수열 XOR 최댓값을 구한다.
모든 태그
주제
#math
10편의 기록
-
-
백준 13710번 XOR 합 3
백준 13710번 XOR 합 3 풀이. 누적 XOR과 비트별 0/1 개수 조합을 이용해 모든 부분수열 XOR 합을 계산한다.
-
백준 2830번 행성 X3
백준 2830번 행성 X3 풀이. 각 비트마다 1과 0의 개수를 세고 조합 수를 곱해 모든 쌍의 XOR 합을 구한다.
-
백준 10464번 XOR
백준 10464번 XOR 풀이. 1부터 n까지의 XOR 패턴과 prefix XOR 관계를 이용해 구간 XOR 값을 상수 시간에 계산한다.
-
백준 11689번 GCD(n, k) = 1
백준 11689번 GCD(n, k)=1 풀이. 오일러 피 함수와 소인수분해를 이용해 n 이하에서 n과 서로소인 수의 개수를 구한다.
-
백준 16563번 어려운 소인수분해
백준 16563번 어려운 소인수분해 풀이. 각 수의 가장 작은 소인수를 미리 저장해 여러 입력을 빠르게 소인수분해한다.
-
백준 2168번 타일 위의 대각선
백준 2168번 타일 위의 대각선 풀이. 가로와 세로 길이, 최대공약수를 이용해 대각선이 지나는 타일 개수를 계산한다.
-
백준 2487번 섞기 순열
백준 2487번 섞기 순열 풀이. 순열을 사이클로 분해하고 각 사이클 길이의 최소공배수를 구해 원래 상태로 돌아오는 시점을 찾는다.
-
백준 2981번 검문
백준 2981번 검문 풀이. 모든 수의 나머지가 같다는 조건을 인접 차이의 최대공약수와 그 약수 문제로 바꿔 해결한다.
-
백준 15824번 너 봄에는 캡사이신이 맛있단다
백준 15824번 너 봄에는 캡사이신이 맛있단다 풀이. 정렬 후 각 원소가 최댓값과 최솟값으로 등장하는 횟수를 거듭제곱으로 계산한다.