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

문제

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

31247번: 2024는 무엇이 특별할까?

 

풀이

약수와 소인수분해는 무척이나 관계가 깊다. 시간복잡도도 동일하고 코드도 동일하다.

N = int(input())
// 약수
div = new set()
for (int i = 0;i <= sqrt(N);i++){
  if (N % i == 0) {
    div.add(i)
    div.add(N/i)
  }
}
// 소인수분해
facto = {}
for (int i = 0;i <= sqrt(N);i++){
  while (N % i == 0) {
  	N = N / i
    facto[i] += 1
  }
}

소인수부터 약수를 구하려면 배열F을 만들고 각 소인수의 개수만큼 소인수를 넣는다.

그 배열에서 가능한 모든 조합에서, 각각의 조합원소의 곱이 약수가 된다.

2가 1개이상 들어간 조합의 원소들을 다 곱한 값이 짝수인 약수이다.

2가 들어가지 않은 조합의 원소들을 다 곱한 값이 홀수인 약수이다.

문제는, 입력제한이 10**18이므로 sqrt(N)의 복잡도로 소인수분해/약수를구한다면 시간내에 구할 수 없단 것이다.

F에서 원소가 2인걸 다 뺀 배열을 O라고하자. 크기는 o이다.

원소가 2인것만 집어넣은 배열을 E라고 하자. 크기는 e이다.

oC0 + oC1 + oC2 + .. oCo = 2^o 가 홀수인 약수의 개수이다. (1도 약수이므로 0개를 선택해도 된다. 소인수분해는 소수(2이상의 값)만 들어간다.)

짝수인 약수들은 2*(모든 홀수 약수) + 4*(모든 홀수 약수) + ... + 2^e * (모든 홀수 약수) 이므로,

짝수인 약수의 개수는 e * 2^o가 된다.

따라서 e * 홀수약수개수 = 짝수약수개수 이다. K = e

e는 N을 2로 몇번 나눌 수 있는지와 동일하다.

따라서 log(N)의 복잡도로 e의 값을 알 수 있다. (N을 2로나눈 나머지가 0이면 계속 2로 나누면 된다.)

2^o를 구할 필요는 없다. 중요한건 K이므로 상수취급하면 된다.

 

문제의 재구성

정확하게 2로 K번 나눌 수 있는 N이하의 수들의 개수를 구하여라. 로 문제를 재구성할 수 있다.

2^K의 배수가 N안에 몇개 있는지 구하려면 int(N/(2^k))를 하면 된다.

하지만 이것은 2^(K+1), 2^(K+2) ...의 배수도 포함될 수 있다.

따라서 int(N/(2^k)) - int(N/2^(k+1)) 을 해서 2^(K+1), 2^(K+2) ...의 배수를 제외해준다.

 

디테일

하지만 K는 10^18까지 올 수 있다. 2^(10^18)을 한다면 컴퓨터는 터진다.

어차피 N보다 큰 2의 거듭제곱수는 계산하면 0이 나올 것이므로 우린 관심없다. 

직접 구하던가, 대충 63이상의 K는 0을 출력한 뒤 무시하도록 짜면 된다. 딱봐도 자료형을 보면 2^63이 10^18보다 클 것이기 때문이다.

 

시간복잡도

O(Tlog(N))