2024는 무엇이 특별할까? (백준 31247)

안녕하세요. 오늘은 2024에 대해서 알아볼 거예요.

문제

https://www.acmicpc.net/problem/31247

아이디어

N=2^t x a라고 합시다. (a는 홀수)
그러면 약수의 개수는 (t+1)x(a의 약수의 개수)가 되고 이중 짝수약수와 홀수약수의 비는 t:1이 됩니다. 이때 t=k가 되어야 하므로 2^K로는 나누어 떨어지지만 2^(K+1)로는 나누어떨어지지 않는 수의 개수를 찾아야 합니다.

N이 2^K보다 크고 2^K로 나눈 나머지를 m이라고 두면 홀수는 조건을 만족하고 짝수는 조건을 만족하지 않습니다. 그러므로 m이하의 홀수의 개수 (m+1)/2를 출력해주면 됩니다.
N이 2^K보다 작다면 0을 출력해주면 됩니다.

소스코드

#include <iostream>
#define ll long long
using namespace std;

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll T, N, K;
    cin >> T;
    while (T--)
    {
        cin >> N >> K;
        while (N && K)
        {
            N /= 2;
            K--;
        }
        cout << (N + 1) / 2 << "\n";
    }
}

감사합니다.