[백준] 11311 - Jug Hard (c++)

https://www.acmicpc.net/problem/11311

 

문제 요약

용량이 각각 a,b인 주전자 두개가 있다. 다음 동작들을 원하는 대로 반복해서 d만큼의 물이 든 주전자를 만들 수 있나?

• 한 주전자에 물 가득 채우기
• 한 주전자에서 다른 주전자로 남은 물 다 붓기 (나머지는 사라짐)

 

풀이 (logN)

• 정수론

d%gcd(a,b)==0을 만족하는 수만 모두 만들 수 있다.

gcd(a,b) 아래론 만들 수 없다-> gcd(a,b)로 나뉘는 수는 만들 수 있다-> 나머지는 만들 수 없다.

이런 순서로 직관에 의존 해 풀어야 한다. 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define mid (st+en>>1)

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc;cin>>tc;
    while(tc--) {
        int a,b,d;cin>>a>>b>>d;
        cout<<(d%__gcd(a,b)?"No":"Yes")<<'\n';
    }
}