B. Math \(n\)에 자연수를 곱하던가 \(n\)을 \(\sqrt n\)으로 만드는 두 연산으로 \(n\)을 최소화하는 문제이다. 문제의 답은 \(n\)의 소인수 하나들만 남긴 것이라는건 금방 알 수 있다. 그러면 연산의 횟수를 구해야하는데, 곱하는건 한 번에 다 곱하면 되고, 제곱근을 구하는 횟수가 문제가 된다. 제곱근을 구할 때마다 소인수들의 차수가 두배씩 줄어드니까 차수가 1이 될때까지의 횟수를 구하면 된다. 이제 완전제곱수들이랑 제곱근을 씌울 필요가 없는 수 같은 것들을 잘 처리해주면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
int main() {
int n, orn;
scanf("%d", &n);
orn = n;
if (n ==1) {
printf("1 0");
return0;
}
bool chk1 =true, chk2 =false, chk3 =false;
int ans =1, mx =0;
for (int i =2;i <= n;++i) {
int cnt =0;
if (n % i ==0) {
ans *= i;
if (mx >0)
chk1 =false;
}
while (n % i ==0) {
cnt++;
n /= i;
}
mx =std::max(mx, cnt);
}
int t =0;
for (int i =1;i <= mx;i *=2) {
if (i == mx) {
chk2 =true;
break;
}
t++;
}
for (longlong i = ans;i <= orn;i *= i)
if (i == orn)
chk3 =true;
printf("%d %d", ans, (chk1 && chk2) || mx ==1|| chk3 ? t : t +1);
C. Banh-mi 구간에서 가장 큰걸 먹어야지 나머지에게도 큰 수치를 나눠줄 수 있으니 내림차순으로 먹는게 무조건 좋다. 다른말로는, 어차피 1과 0밖에 없으니 1부터 먹고 다 먹은 후에 0을 먹는게 이득이다. 그래서 식으로 써서 정리하다보면 최대치는 \((2^{\text{1의 개수}}-1)(2^{\text{0의 개수}}-1)+1\)이라는 식이 나온다. 이 결과를 매 쿼리마다 출력하면 된다. 1의 개수와 0의 개수를 구간합으로 잘 구하면 된다. 나는 펜윅트리를 썼는데, 업데이트가 없으니 그냥 prefix sum으로 구해도 된다. 사실 펜윅트리를 쓴다고 시간초과가 나는 문제들은 많지 않긴 하지만, 구간합을 구하라고 하면 펜윅트리를 쓰게되는 안 좋은 버릇이 생긴 것 같다.
D. Fun with Integers 약수 배수 관계인 것들 사이에 서로 변환이 가능한데, 변환하면서 곱하거나 나눠진 수의 절댓값의 합을 구하는 문제다. 그래프문제같아보이기도 하지만, 중요한 점은 어떤 수의 약수들만 모두 변환이 가능하다는 것이다. 그리고 음수->음수, 음수->양수, 양수->음수, 양수->양수의 4가지 경우가 있으니 결국 문제에서 구하라는건 \(1\)부터 \(n\)까지의 모든 수의 약수의 합에 \(4\)를 곱한 값이다.
