1542B. Сложить и умножить

#include <bits/stdc++.h>

#define lli long long int

#define all(x) x.begin(), x.end()
#define in(x, y) y.find(x) != y.end()
#define not_in(x, y) y.find(x) == y.end()

using namespace std;


void print(auto &data, auto sep=", ", auto end=endl)
{
    cout << "[";
    for (auto i: data)
    {
        cout << i << sep;
    }
    cout << "]" << end;
}


int main()
{
    lli t, n, a, b;
    bool TF;

    cin >> t;
    while (t--)
    {
        cin >> n >> a >> b;

        if (n == 1 || n % a == 0)
        {
            cout << "Yes\n";
        } else if (a == 1)
        {
            cout << ((n % b == 1)?"Yes":"No") << "\n";
        } else
        {
            set<lli> front;
            set<lli> old_front;
            set<lli> new_front;

            front.insert(1);

            TF = false;
            while (!front.empty())
            {
                new_front.clear();

                old_front.insert(all(front));
                for (auto i: front)
                {
                    if (i * a == n || i + b == n)
                    {
                        TF = true;
                        break;
                    }

                    if (i * a <= n - b && not_in(i * a, old_front))
                    {
                        new_front.insert(i * a);
                    }

                    if (i + b <= n - b && not_in(i + b, old_front))
                    {
                        new_front.insert(i + b);
                    }
                }

                // print(old_front);
                // print(new_front);
                // cout << "\n";

                if (TF)
                {
                    break;
                }

                front.clear();
                front.insert(all(new_front));
            }

            cout << ((TF)?"Yes":"No") << "\n";
        }
    }

    return 0;
}