Codeforces Round #781 (Div.2)

https://codeforces.com/contest/1665

Dashboard - Codeforces Round #781 (Div. 2) - Codeforces

A - GCD vs LCM (00:02)

1 (n - 3) 1 1

 

B - Array Cloning Technique (00:10)

가장 많은 수의 개수를 k라고 하면, k는 계속 2배가 된다. 그냥 구현하면 된다.

 

B - Tree Infection (01:25)

루트를 기준으로 층을 나누고, 각 자식 노드의 수를 배열 c에 저장한다. 여기서 자식 노드의 수가 큰 정점부터 그리디하게 해결하면 된다.

 

D - Array Cloning Technique (--:--)

gcd(x+a, x+b) = gcd(x+a, b-a)임을 이용해서, b=2a로 고정해서 gcd(x+a, a)로 만든다.

gcd(x+a, a) = gcd(a, x)이고, 비트로 봐서 계산하면 된다.

정확히 30번의 쿼리로 실행 가능하다