목록2025/04/03 (1)
jay153의 PS 일지
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..
CodeForces
2025. 4. 3. 11:00