链接：https://ac.nowcoder.com/acm/contest/49343/D
ygg的分数运算
题目描述
\[给定两个数 a, b ( a, b 都是质数)。 问是否可以通过对分数 \frac{1}{a} , \frac{1}{b} 通过百亿次以内的加法乘法，使得结果的分母为c \]例如 a = 2， b = 3， c = 18
\[我们有 \frac{1}{2} + \frac{1}{3} = \frac{5}{6} , \frac{5}{6} * \frac{1}{3} = \frac{5}{18} \]输入描述:
\[三个数a,b,c,2\le a,b,c \le 10^9,2≤a,b,c≤10^9 (a，b都是质数)\]输出描述:
\[如果可以，输出YES，否则输出NO \]分析：
作为菜鸡首先想到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;
}