[백준] #31247 2024는 무엇이 특별할까? - 파이썬

문제

백준 온라인 저지의 신년대회 Hello, BOJ 2024!의 개최일은 2024년 1월 14일이다. 정휘는 대회가 개최된다는 사실이 기뻐 제목을 뚫어져라 보다가 2024가 무언가 특별하다는 사실을 깨달았다.

그렇다. τo(n)$\tau_o(n)$을 n의 약수이면서 홀수인 양의 정수의 개수, τe(n)$\tau_e(n)$을 n$n$의 약수이면서 짝수인 양의 정수의 개수라고 할 때, τe(2024)=3τo(2024)$\tau_e(2024) =3\tau_o(2024)$을 만족한다. 다음에 이런 연도가 오려면 16년 뒤인 2040년이 되어야 한다.

 τe(x)=K×τo(x)$\tau_e(x) =K\times\tau_o(x)$를 만족하는 양의 정수 x$x$를 K$K$-특별한 수라고 정의하자. 양의 정수 N$N$과 음이 아닌 정수 K$K$가 주어진다. N$N$ 이하의 양의 정수 중 K$K$-특별한 수의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T$T$가 주어진다.

이후 T$T$개의 줄에 걸쳐 테스트 케이스가 한 줄에 하나씩 주어진다. 각 테스트 케이스는 한 줄로 구성되어 있으며, 각각 양의 정수 N$N$과 음이 아닌 정수 K$K$가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스마다, 한 줄에 하나씩 N$N$ 이하의 양의 정수 중 K$K$-특별한 수의 개수를 출력한다.

제한

•  1≤T≤100000$1\le T\le 100\, 000$ 
•  1≤N≤1018$1\le N\le 10^{18}$ 
•  0≤K≤1018$0\leq K\leq 10^{18}$ 

예제 입력 1 복사

5
1 0
9 2
17 2
20 3
100 1000000000000000000

예제 출력 1 복사

1
1
2
1
0

---

복기

1. 그냥 구현했더니 시간초과가 났다..
2. 수가 매우 클때는 그냥 input()말고, sys.stdin.readline()을 쓰자.

import sys

sys.stdin.readline() # input()과 동일

 

3.x를 2의 거듭제곱으로 나눈후 남는 홀수 부분이 같으면 홀수 약수 개수는 같다.

즉, K-특별한 수는 어떤 수 x가 2^k를 약수로 갖고, 그 다음 2를 한번 더 나누면 홀수로 떨어지는 수다.

(너무 어렵네..)

---

솔루션

import sys

T = int(sys.stdin.readline())
for _ in range(T):
    N, K = [int(x) for x in sys.stdin.readline().split()]
    print((N >> K) - (N >> (K + 1))) # 수 x가 2^K의 배수지만 2^(K+1)의 배수가 아니어야 함