Educational 139 div2 virtual

https://codeforces.com/contest/1766

Dashboard - Educational Codeforces Round 139 (Rated for Div. 2) - Codeforces

A. 

n이 주어지고 1<=x<=n범위의 모든 x에 대해서 단 하나의 digit만 0이 아닌 수인 x의 개수

간단하게 자릿수마다 9개씩 근데 이 자릿수가 최상위 자리수라면 그 수만큼 더해주면 된다.

 

B.

operation이 두 개 존재 

1. substring을 복붙해서 뒤에 넣기

2. 아무문자나 뒤에 넣기 

 

연산을 최대 n-1번 해서 주어진 문자열과 같게 만드는 것이 가능한지 

 

2번 연산만 적용해서 n번에 가능하다.

따라서 1번의 연산만 1번 operation 적용이 가능하다면 n-1번 이하로 가능하게 된다.

 

그러므로 인접한 두개에 대해서 저장을 하고 앞에 나오는 두개의 문자열이 이미 저장된 문자열인지 파악한다. 

 

C.

(2, M)의 격자에서 W,B 블록이 존재하고 

B로만 이동이 가능하다

 

인접한 블록을 통해서만 이동하며 모든 B을 다 도달할 수 있는지 문제

 

어떤 점을 왼쪽에서 오른쪽으로 이동시키자 이 경우 그 상태에서 이동할 수 있는 방향은 단 한가지 방향이다. 

따라서 최초 상태 두가지에 대해서만 bfs를 돌리면 된다.

 

D.

문제를 보고 gcd 유클리드 호제법이 떠오르긴 했지만 아무리 봐도 파악할 수 없었다. 

그래도 최대 공약수문제이니 두 수의 공약수와 관련이 있겠다 생각해서 그걸 중점적으로 파악

 

차이와 연관이 있다는 것을 알게되고 차이의 배수가 되어야 되지 않을까 생각을 하였다. 

 

예제는 10009와 20000이고, 답은 97 하지만 두 수의 차이는 9991로 10088은 9991의 배수가 아니다. 

 

9991을 소인수분해 해보니 97이 소인수중 하나였고 이걸로 파악

 

식을 세워봄 

 

A+D, A를 1씩 더했을 때 최초로 어떤 동일한 수로 나누어 떨어지려면 

우선 D가 나누어 떨어져야 하고, A+K가 나누어 떨어져야 하므로 

A+K는 D의 소인수의 배수가 되어야 한다. 

 

근데 여기서 D의 소인수중 가장 작은것만 조사하는 것이 아니라 당연하게도 모든 D의 소인수를 조사

 

단순하게 sqrt(N)소인수 분해를 하게 되면 

O(N*sqrt(10^7)*log(10^7)) 의 시간복잡도가 나옴

 

이걸 줄이기 위해서 linear sieve를 이용해서 10^7의 모든 수에 대해서 소인수를 구하고 처리하면 된다.