链接：https://ac.nowcoder.com/acm/contest/49343/D

ygg的分数运算

题目描述

例如 a = 2， b = 3， c = 18

输入描述:

输出描述:

分析：

作为菜鸡首先想到DFS，毫无疑问T了

void dfs(int u)
{
    if (u > c || f)
    {
        return;
    }
    if (u == c)
    {
        f = true;
        return;
    }

    dfs(u * a);
    u /= a;
    dfs(u * b);
    u /= b;
}

换思路：
对于a，b：

• a == b时，c 只能由 a 不断相乘获得
• a != b时，c 只能由一些 a 与一些 b 相乘得到

考虑被约分的情况，都是质数约分后还是可以表示成一些 a 与一些 b 的乘积形式 qwq

#include <bits/stdc++.h>
using namespace std;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define x first
#define y second
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 200010, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
typedef unordered_map<int, int> Ump;
int T;
int a, b, c;
bool f = false;
void solve()
{
    cin >> a >> b >> c;
    // dfs(1);
    while (c % a == 0)
        c /= a;
    while (c % b == 0)
        c /= b;
    if (c == 1)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}
signed main()
{
    FAST;
    // cin >> T;
    T = 1;
    while (T--)
        solve();
    return 0;
}