AtCoder Beginner Contest 357 문제 분석 및 풀이
A - 손 소독하기
N명의 외계인이 순차적으로 손을 소독하려고 합니다. 각 외계인은 H_i개의 손을 가지고 있으며, 전체를 소독해야 합니다. 소독제는 총 M회 사용할 수 있습니다. 한 외계인이 소독을 할 때 필요한 양만큼만 사용하며, 부족하면 남은 양만 소모합니다. 모든 손을 소독한 외계인의 수를 구하세요.
단순히 앞에서부터 순회하면서 소독제 잔량을 갱신하고, 소진 ...
6월 13일 19:05에 게시됨
동일 방정식과 확장 유클리드 알고리즘
x와 y의 최대공약수가 d일 때
(x,y)=d
방정식으로 변환하면
ax+by=d
매개변수 x와 y에 대한 표현식 x y의 부호는 상관없음
x=x0+kb/d (반대쪽을 더함)
y=y0-ka/d
//확장 유클리드 알고리즘
int extended_gcd(int a, int b, int &x, int &y)//ax=d%(mod b) x와 y는 ax+by=d 방정식의 한 해 반환값은 최대공약수(마지막 레이어의 a)
{
if (!b)
{
x ...
6월 6일 21:47에 게시됨