CF1542B Plus and Multiply

CF1542B Plus and Multiply - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

\(T = \{a^x +yb \text{ } \vert \text{ } x, y \in N\}\) 和 \(S\) 相等。

证明：

• \(S \subseteq T\)：显然有 \(1 \in T\)。然后有 \((a^x+yb) \times a = a^{x+1} + (ay)b\)，\((a^x + yb) + b = a^{x+1} + (y+1)b\)。
• \(T \subseteq S\)：\(a^x + yb\) 可以由 \(1\) 乘 \(x\) 次 \(a\) 再加 \(y\) 次 \(b\) 得到。

因此 \(S = T\)。

那么问题可以转化为 \(n\) 是否可以表示为 \(a^x + yb\)，其中 \(x, y \in N\)？

容易发现当 \(a \ne 1\) 时，\(x\) 的范围很小。枚举 \(x\) 即可。然后检验 \(y\) 是否为 \(n - a^x\) 的因数。

\(a = 1\) 时容易特判：只需要检验 \(n \bmod b = 1\) 或 \(b = 1\) 即可（注意 \(X \bmod 1 = 0\)）。

单组数据 \(\mathcal{O}(\log n)\)。

/*
 * @Author: crab-in-the-northeast 
 * @Date: 2022-10-14 01:41:35 
 * @Last Modified by: crab-in-the-northeast
 * @Last Modified time: 2022-10-14 01:52:57
 */

#include <bits/stdc++.h>
#define int long long

inline int read() {
    int x = 0;
    bool flag = true;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            flag = false;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    if(flag)
        return x;
    return ~(x - 1);
}

signed main() {
    int T = read();
    while (T--) {
        int n = read(), a = read(), b = read();
        if (a == 1) {
            if (b == 1 || n % b == 1)
                puts("Yes");
            else
                puts("No");
            continue;
        }

        bool fl = false;
        for (int X = 1; X <= n; X *= a) {
            if ((n - X) % b == 0) {
                fl = true;
                break;
            }
        }

        puts(fl ? "Yes" : "No");
    }
    return 0;
}