백준 - 27981번 압도적 XOR 수 (수학)

무지성 시도 방법

# N의 범위가 1부터 10^15 이므로 A를 1개씩 늘려서 찾는 무지성 Brute Force는 먹히지 않아 나름 규칙성을 찾아 구현한 방법이나 역시나 시간초과...

N,k=map(int,input().split())
# 양의 정수 A에 대해 A보다 큰 2의 제곱 수 중 가장 작은 값을 구하는 함수
def P1A(A):
    k = A.bit_length()
    return ((1<<k) - A -1)      # 비트연산자보다 -/+ 연산자의 우선순위가 빠르므로 비트연산자 결과를 괄호로 묶음
    

# B라는 수는 A XOR (P-1)로 정의하며
# P-1이라는 수는 A 이진수의 모든 자리 수에 1이 들어간 수 이므로 
# A XOR (P-1) 은 결국 (P-1) - A를 뺀 값이 된다.
# Ex. A = 10 -> A(2) : 1010, P = 16, P-1(2) : 1111(15)
# 1010 XOR 1111 -> 0101 -> 5 = 15 - 10
# 즉 B는 P-1-A로 정의할 수 있다.

# 양의 정수 K에 대해 A >= B*(1<<K-1)일 경우를 다시 쓰면
# A >= (P-1-A)*(1<<K-1) 이며
# 즉 P를 2의 제곱수로 2배씩 증가시키면서 적합한 A를 찾으면 될 것 같다?
# 이 때 식을 보면 P-1-A = 0 인 경우 비교 관계가 A >=0으로 항상 성립함을 알 수 있으므로
# 최소 A의 개수는 N 보다 작거나 같은 2의 제곱 수 -1 을 가진다 (Ex. 1, 3, 7, 15, ...)
# 아니면 P-1-A가 0인 경우, 1인 경우, 2인 경우로 늘려가면서 찾는 방법도 있을 것 같고..

# 이렇게 짜면 답은 나오지만 아주 큰 수가 나오면 시간 초과가 된다...
cnt = 0
A = 1
p = 1
while(A<=N):
    if A < 1<<k:
        print("A: ", A)
        cnt+=1
        p+=1
        A=(1<<p) - 1
    else:
        while(A>=P1A(A)*((1<<k)-1)):
            print("P-1-A: ", P1A(A))
            print("A: ", A)
            cnt+=1
            A-=1
        p+=1
        A=min((1<<p)-1,N)
        
    
    if (N < (1<<p-1)): break
        

print(cnt)

규칙성 심화(는 6%따리 실패... 조금 더 정교하게 코드를 짜야겠다 ㅠ)

# 243 4인 경우 
# 가능한 A는 
# 1,3,7,15 로 4개에 다다시
# 31,30 -> 2개
# 63,62,61,60 -> 4개
# 127,126,125, ... 120 -> 8개
# 255, ... 240 -> 16개 중 243보다 작은 4개 이런 식으로 늘어남을 알 수 있으므로 
# 이 규칙성을 수식으로 표현하자면


# N이 243이기 때문에 Nk=8이 된다.

# 1. A가 1<<k보다 작은 경우 가능한 A는 k개로 예제의 경우 : 4개
# 2. A가 1<<k 보단 크지만 1<<(Nk-1) 보다 작은 경우는 (1<<(Nk-k)) -2 개로 예제의 경우 : 16-2개
# 3. A가 1<<(Nk-1)보단 크지만 1<<(Nk)보다 작은 경우는 N - (1<<Nk) - (1<<(Nk-k)) + 1로 예제의 경우 243 - (256-16) + 1 : 4개

# 종합하면
# A의 개수는 k-2 + (1<<(Nk-k)) + (N-((1<<Nk)-(1<<(Nk-k))) + 1로
# 요약하면 A의 개수는 N+k-1 + (1<<(Nk-k+1))*(1-(1<<(k-1)))
# 이지만 주어진 N의 Nk 값을 고려하여 k를 정의하여 
# 1. 만약 Nk가 k를 비교하여 Nk가 k보다 작거나 같다면 k를 Nk의 값으로 갱신하고
# 2. Nk가 k 보단 크지만 범위를 나눠야 한다.

# 1. N이 1<<k보다 작은 경우 즉 Nk < k 인 경우
N,k=map(int,input().split())
Nk=(N+1).bit_length()
if Nk<=k:
    print(Nk-1)
else:
    tot = k + max(0,N-1+((1<<(Nk-k+1))*(1-(1<<(k-1)))))
    print(tot)