寂静的角落 星空在前,路在脚下
Plus and Multiply
发布于: 2021-07-05 更新于: 2021-07-05 分类于: 题解 阅读次数: 

做了半天才发现其实很简单……

Plus and Multiply

提交地址:洛谷 CF1542BCodeForces CF1542B

题目大意

有一个集合:

  • $1$ 在集合中。
  • 如果 $x$ 在集合中,那么 $x \cdot a$ 和 $x + b$ 在集合中。

给定 $a, b, n$ 判断 $n$ 是否在集合中。

分析

我们发现,有 $(a^{x_1} + y_1 \cdot b) \cdot a^{x_2} + y_2 \cdot b = a^{x_1 + x_2} + b \cdot (y_1 \cdot a^{x_2} + y_2)$,由于 $x$ 和 $y$ 是我们任意取的,那么 $y_1 \cdot a^{x_2} + y_2$ 可以用一个 $y$ 来表示,则上式化简为 $a^x + b \cdot y = n$。

将上式转化为 $n - a^x \equiv 0 \pmod b$, 这样我们直接枚举指数 $x$ 即可,复杂度为 $\Omicron(\log_an)$。

$\rm\color{green}code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cctype>
#include <cstdio>
using namespace std;
typedef long long ll;
template <typename T = int>
inline T qread() {
T n = 0;
bool flag = false;
char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') flag = true, c = getchar();
while (isdigit(c)) n = (n << 3) + (n << 1) + (c ^ 48), c = getchar();
return flag ? -n : n;
}
int t;
ll a, b, n;
bool flag;
int main() {
t = qread();
while (t--) {
n = qread<ll>(), a = qread<ll>(), b = qread<ll>();
if (a == 1) { // 注意这里要特判,如果 a 为一不特判会死循环
puts((n - 1) % b == 0 ? "Yes" : "No");
continue;
}
flag = false;
for (ll i = 1; i <= n; i *= a)
if ((n - i) % b == 0) {
flag = true;
break;
}
puts(flag ? "Yes" : "No");
}
return 0;
}
本文默认采用 署名-非商业性使用-相同方式共享 4.0 国际 许可证