A+B (백준 9267)

안녕하세요. 오늘은 더할 거예요.

문제

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

아이디어

ax+by=S를 만족하는 x,y (x>0 && y>0 && gcd(x,y)=1)이 존재하는지 확인하면 됩니다.
세가지 방법을 다르면 됩니다.

a,b,S의 값이 0이면 곤란하므로 예외처리를 한다.
ax+by=1의 근을 찾고 (x,y)에 S를 곱한다. 당연하지만 gcd(a,b)가 S를 나누지 않는다면 "NO"이다.
x,y중 하나는 음수가 나올텐데 양수인 값이 최소의 양수가 되게 하고 음수를 최대한 끌여올린다. 이때 그 음수였던것을 다시 조금씩 내리면서 gcd값이 1이 되는지 확인하면 된다.

오버플로우 문제 때문에 int128을 씁니다.
하지만 그러면 입력에서 >> 오퍼레이터를 쓸 수 없기 때문에 입력은 long long 으로 받고 연산만 int128로 해주면 됩니다.

소스코드

#include <iostream>
#include <algorithm>
#define ll __int128
using namespace std;

ll gcd(ll a, ll b) { return ((b) ? gcd(b, a % b) : a); }
pair <ll, ll> cal(ll a, ll b) //ax+by=1 정수해 (x,y)
{
    if (a == 1) return { 1,0 };
    if (b == 1) return { 0,1 };

    bool swapped = false;
    if (a < b)
    {
        swap(a, b);
        swapped = true;
    }

    ll temp1 = a / b, temp2 = a % b;
    pair <ll, ll> temp = cal(temp2, b);
    pair <ll, ll> Ans = { temp.first,-temp1 * temp.first + temp.second };

    if (swapped) swap(Ans.first, Ans.second);
    return Ans;
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    long long aa, bb, ss;
    cin >> aa >> bb >> ss;

    ll a, b, S;
    a = aa; b = bb; S = ss;

    if (S == 0)
    {
        if (a > 0 && b > 0) cout << "NO";
        else cout << "YES";
        return 0;
    }
    if (a == 0)
    {
        if (b == 0) cout << "NO";
        else
        {
            if (S % b == 0) cout << "YES";
            else cout << "NO";
        }
        return 0;
    }
    if (b == 0)
    {
        if (S % a == 0) cout << "YES";
        else cout << "NO";
        return 0;
    }
    if (a == S || b == S)
    {
        cout << "YES";
        return 0;
    }

    ll g = gcd(a, b);
    if (S % g != 0)
    {
        cout << "NO";
        return 0;
    }
    a /= g; b /= g; S /= g;

    pair <ll, ll> temp = cal(a, b);
    ll x = temp.first, y = temp.second;

    x *= S; y *= S;

    bool swapped = false;
    if (x < y)
    {
        swap(x, y);
        swap(a, b);
        swapped = true;
    }

    ll num1 = (x - 1) / b;
    y += num1 * a; x -= b * num1;
    
    while (y > 0)
    {
        if (x > 0 && y > 0 && gcd(x, y) == 1)
        {
            cout << "YES";
            return 0;
        }
        x += b;
        y -= a;
    }

    cout << "NO";
}

감사합니다.