CodeForces Round 942 - Div 1

https://codeforces.com/contest/1967

 

Performance Rating : 2400

 

A

$k$를 적절히 분배해서 $a_i$의 최솟값을 크게 만들고 최솟값의 개수를 줄이는 것이 좋은 전략인 것을 눈치채고 적절히 분배하는 방법으로는 파라메트릭 서치가 적절해 보여서 이를 구현했다.

 

B1

$\frac{a+b}{b\cdot \mathrm{gcd}(a,b)}$가 정수이기 위해서는 $\frac{a+b}{b}$가 정수여야 하므로 $a$가 $b$의 배수인 것을 생각했다. $a=kb$라고 했을 때 $\mathrm{gcd}(a, b)=b$이므로 $\frac{k+1}{b}$가 정수여야 하는데 이때 $b$를 고정하면 $k+1=pb$이라는 사실을 알 수 있고 $a=(pb-1)b$가 되므로 $a$를 $b^2$으로 나눈 나머지가 $b$여야 한다. 그러므로 $b$를 $1$부터 $m$까지 증가시키면서 가능한 $a$의 개수를 모두 더하는 방식으로 해결했다.

 

B2

우선 $\mathrm{gcd}(a, b)=g$라고 하고 $a=a'g$, $b=b'g$로 나타내었다. 이를 대입하면 $\frac{b'g}{a'+b'}$이 되는데 $\mathrm{gcd}(a', b')=1$이므로 $\mathrm{gcd}(a'+b', b')=1$이고 결국 $g$가 $a'+b'$의 배수여야 한다는 것을 생각하고  $g$를 $1$부터 늘리면서 답을 구해보자는 생각을 했다..  $a+b\leq m+n$이므로 $a'+b'\leq (m+n)/g$이고 그러면 $a'+b'$의 범위가 $2$부터 $\mathrm{min}(g, (m+n)/g)$이므로 해당하는 범위에 있는 $a'+b'$ 중 $g$의 약수인 것에서 $\mathrm{gcd}(a',b')=1$인 것의 개수를 세어 더해주었다.

 

C

복잡도를 $O(nlogk)$로 줄이자는 최종 목표를 가지고 문제를 풀기 시작했다. 빠른 거듭제곱을 하듯이 $2^i$번 변환을 한 것을 한 번에 역변환시킬 방법을 계속해서 고민했고 $2^{i-1}$번을 역변환하는 방법을 저장해 두고 이를 활용하면 $2^i$번을 역변환할 수 있겠다는 생각을 했다. 그러나 아이디어를 떠올리는 과정과 구현을 하는 과정 모두 오래 걸렸다.