题目链接：https://ac.nowcoder.com/acm/contest/11256/G
题目大意：给你(a,b,c)，求满足(lcm(a+x,b+y)=c)的最小的(x+y)值
题目思路：设(A=a+x,B=b+y)，给的(n)和(k_i)很小，最多只有18，可以dfs暴力枚举所有符合条件的(A)和(B)，通过剪枝优化可以AC，具体看代码吧，另外这个题数字很大，需要用int128输入输出
思路和代码我参考的这位大佬nagisa_菜鸡
AC代码：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <deque>
#include <queue>
#include <cmath>
#include <map>
#include <set>
using namespace std;
template <typename T>
void write(T x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
namespace FastIO
{
const int SIZE = 1 << 16;
char buf[SIZE], str[64];
int l = SIZE, r = SIZE;
int read(char *s)
{
while (r)
{
for (; l < r && buf[l] <= ' '; l++)
;
if (l < r)
break;
l = 0, r = int(fread(buf, 1, SIZE, stdin));
}
int cur = 0;
while (r)
{
for (; l < r && buf[l] > ' '; l++)
s[cur++] = buf[l];
if (l < r)
break;
l = 0, r = int(fread(buf, 1, SIZE, stdin));
}
s[cur] = ' ';
return cur;
}
template <typename type>
bool read(type &x, int len = 0, int cur = 0, bool flag = false)
{
if (!(len = read(str)))
return false;
if (str[cur] == '-')
flag = true, cur++;
for (x = 0; cur < len; cur++)
x = x * 10 + str[cur] - '0';
if (flag)
x = -x;
return true;
}
template <typename type>
type read(int len = 0, int cur = 0, bool flag = false, type x = 0)
{
if (!(len = read(str)))
return false;
if (str[cur] == '-')
flag = true, cur++;
for (x = 0; cur < len; cur++)
x = x * 10 + str[cur] - '0';
return flag ? -x : x;
}
} // namespace FastIO
using FastIO::read;
typedef __int128 int128;
typedef pair<int, int> PII;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int N = 110, M = 1e5;
const int base = 1e9;
const int P = 131;
const int mod = 998244353;
const double eps = 1e-6;
int n;
int128 a, b, c;
int128 pk[N];
int128 p[N], k[N];
int128 remain[N];
int128 ans;
void dfs(int u, int128 A, int128 B)
{
if (A * remain[u] < a || B * remain[u] < b) //当前值和剩余所有的因数的乘积不够大
return;
if (A - a + B - b > ans) //当前求出的值不满足最优
return;
if (u > n)
{
ans = min(ans, A - a + B - b);
return;
}
int128 pi = 1;
for (int i = 1; i <= k[u]; ++i)
{
dfs(u + 1, A * pi, B * pk[u]);
dfs(u + 1, A * pk[u], B * pi);
pi *= p[u];
}
dfs(u + 1, A * pk[u], B * pk[u]); //减少一次dfs
}
int main()
{
read(n);
c = 1;
for (int i = 1; i <= n; ++i)
{
read(p[i]), read(k[i]);
pk[i] = 1;
for (int j = 1; j <= k[i]; ++j)
pk[i] *= p[i];
c *= pk[i];
}
remain[n + 1] = 1;
for (int i = n; i >= 1; --i)
remain[i] = remain[i + 1] * pk[i];
read(a), read(b);
ans = 2 * c;
dfs(1, 1, 1);
write(ans);
return 0;
}