2O21년 1월 13일 PS 일지

오늘은 블로그에 글을 쓰는 날! 이 PS일지로 대신하자.

 

이론 글 쓰는건 정말 귀찮다r.

 

1.롯데 자이언츠와 가희

1. www.acmicpc.net/problem/20653

20653번: 롯데 자이언츠와 가희

조가희님이 오픈톡방에 올린 문제!

 

어떤 수 X가 주어졌을 때 

n개의 수가 각각 d1^e_i_1 * d2^e_i_2 * d3^e_i_3 ... 의 꼴로 표현될 때 (d_i는 소수, e_i는 음이 아닌 정수)로 표현된다면

d1^max(e_1) * d2^max(e_2) .... =  X가 되는

n개의 수의 순서쌍의 가짓수를 구하는 문제다.

이때 모든 i에 대해 min(e_i) = 0이어야 한다.

 

X를 소인수분해하면 max(e_i)는 쉽게 구할 수 있다. 각 i에 대해 가짓수를 따로 구한다음 곱해주면 된다.

 

조합론에서 많이 쓰이는 테크닉 -> 포함과 배제

min (e_i) = 0 조건을 잠깐 빼보자.

어떤 i에 대해 max(e_i) = p라 하면

그 가짓수는 $(p+1)^n - p^n$이 된다. 왜?

n개의 수에 대해 각각 0~p의 지수가 가능하고 모든 수가 0~p-1을 선택하는 경우를 빼면 답이 나온다.

다시 min(e_i)=0 조건을 넣으면

모든 수가 1 이상인 경우를 빼주면 된다.

모든 수에서 1을 빼주자. 그러면 이제 아까 구한 상황 그대로에서 p만 1 감소한 것이다.

 

결론적으로 답은 $(p+1)^n - p^n - (p^n - (p-1)^n)$이 된다.

 

이제 각 소인수의 지수에 대해 위 값을 곱해서 모듈러를 해주면 된다.

n이 최대 100만이므로 분할정복을 이용하여 최적화하자.

 

시간복잡도는 테스트 케이스 당 $O(log N*sqrt(N))$ 이다.

 

1일 3BOJ라는 오픈카톡방에 들어갔는데 당분간 해보자.

 

2. 금민수의 합

www.acmicpc.net/problem/1528

3. 염소 줄서기 - Diamond 4!!!

www.acmicpc.net/problem/2060

 

위 문제들은 아래 게시물에 풀이를 적었다.

2021/01/12 - [Problem Solving] - 머리로만 문제 풀기

 

여담으로, 염소 줄서기 문제는 백준님이 푸신 4개의 다이아 문제 중 하나다.

(백준님이 푸신 문제는 꿀다이아가 분명해! 라는 생각으로 골랐다 ㅎ..)

 

+ 문제 중에 최소 외접원 문제가 하나 있길래 담금질 기법 사용한거 공부한 다음

 전에 안 푼 최소 외접원 문제들을 모조리 AC 받고 왔다.

 

Convex hull도 복습했는데, 최소 외접원을 구할 때 Convex Hull에 대해서만 구하면 시간복잡도를 많이 줄일 수 있다.

+ 암기하자. w = 0.1, dw = 0.995