사용자 도구

사이트 도구


ps:problems:boj:31247

2024는 무엇이 특별할까?

ps
링크acmicpc.net/…
출처BOJ
문제 번호31247
문제명2024는 무엇이 특별할까?
레벨실버 1
분류

수학

시간복잡도O(T)
인풋사이즈T<=100000
사용한 언어Python 3.11
제출기록31120KB / 196ms
최고기록196ms
해결날짜2024/01/15

풀이

  • a의 약수들을 d1,d2,…,dl 라고 하자.
  • a가 홀수라면 d1,d2,…,dl는 모두 홀수이다.
  • 2^m*a의 약수는 di들과 2*di,2^2*di,2^3*di,…,2^m*di 들이다. di들만 홀수이고 나머지는 모두 짝수이므로, 짝수인 약수의 개수는 홀수인 약수의 개수의 m배가 된다
  • 따라서, K-특별한수의 개수는 2^k*{홀수} 형태의 수의 개수와 동일하다. N이하의 2^k*{홀수} 형태의 수의 개수는 2^k의 배수의 개수에서 2^(k+1)의 배수의 개수를 빼는 방식으로 구할 수 있다. 시간복잡도는 O(1)

코드

"""Solution code for "BOJ 31247. 2024는 무엇이 특별할까?".

- Problem link: https://www.acmicpc.net/problem/31247
- Solution link: http://www.teferi.net/ps/problems/boj/31247

Tags: [math]
"""

import sys


def main():
    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)))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
I G T S Q
 
ps/problems/boj/31247.txt · 마지막으로 수정됨: 2024/01/15 08:43 저자 teferi