一、题意理解

我们要求是否存在正整数 $n$，使得在 $k$ 进制下，$a \times n$ 的数位和 $S_k(a \cdot n)$ 满足： $S_k(a \cdot n) \equiv c \pmod{b}$ 其中 $a,b,c,k$ 给定。

---

二、初步观察

设 $n$ 是正整数，$m = a \cdot n$。

在 $k$ 进制下，$m$ 的数位和 $S_k(m)$ 有一个重要性质： $S_k(m) \equiv m \pmod{k-1}$ 这是因为 $k \equiv 1 \pmod{k-1}$，所以 $k^t \equiv 1 \pmod{k-1}$，因此 $m$ 的各位加权和模 $k-1$ 等于数位和模 $k-1$。

于是： $S_k(a \cdot n) \equiv a \cdot n \pmod{k-1}$

---

三、问题转化

我们要求： $S_k(a n) \equiv c \pmod{b}$ 利用上述同余性质，这等价于： $a n \equiv S_k(a n) \equiv c \pmod{\gcd(b, k-1)}$ 记 $g = \gcd(b, k-1)$，则必要条件为： $a n \equiv c \pmod{g}$

---

1. 必要条件

设 $d = \gcd(a, g)$。
方程 $a n \equiv c \pmod{g}$ 有解当且仅当 $d \mid c$。

如果 $d \nmid c$，则直接输出 No。

---

四、充分性讨论

如果 $d \mid c$，那么 $a n \equiv c \pmod{g}$ 有解 $n_0$。

但是我们需要的是 $S_k(a n) \equiv c \pmod{b}$，而不仅仅是 $a n \equiv c \pmod{g}$。

实际上，$S_k(m) \equiv m \pmod{k-1}$ 是严格成立的，所以： $S_k(a n) \equiv a n \pmod{k-1}$ 而 $g \mid (k-1)$，所以 $S_k(a n) \equiv a n \pmod{g}$。

因此，如果 $a n \equiv c \pmod{g}$，则 $S_k(a n) \equiv c \pmod{g}$。

但我们要求模 $b$，而不仅仅是模 $g$。

---

五、关键点

我们还需要 $S_k(a n) \equiv c \pmod{b}$。

因为 $g = \gcd(b, k-1)$，所以 $b = g \cdot r$，其中 $\gcd(r, k-1/g) = 1$。

条件 $S_k(a n) \equiv c \pmod{b}$ 等价于： $ S_k(a n) \equiv c \pmod{g} \quad \text{且} \quad S_k(a n) \equiv c \pmod{r} $ 第一个条件已经由 $a n \equiv c \pmod{g}$ 保证（因为 $S_k(a n) \equiv a n \pmod{g}$）。

第二个条件 $S_k(a n) \equiv c \pmod{r}$ 能否满足？

---

六、构造方法

已知 $a n \equiv c \pmod{g}$，设 $a n = c + t g$。

我们能否通过调整 $t$ 使得 $S_k(a n) \equiv c \pmod{r}$ 也成立？

注意 $S_k(m)$ 可以取很多不同的值，因为我们可以让 $m$ 在 $k$ 进制下包含很多高位，从而让数位和变化。

因此，我们可以通过加 $k^L(k-1)$ 来让数位和增加 $k-1$。

---

因为 $\gcd(r, k-1) = 1$（因为 $r = b/g$，而 $g = \gcd(b, k-1)$，所以 $\gcd(r, k-1) = 1$），所以 $k-1$ 在模 $r$ 下有逆元。

于是我们可以通过加若干个 $k^L(k-1)$ 来调整 $S_k(m)$ 模 $r$ 的值，使其等于 $c$。

---

七、结论

因此，充要条件就是： $\gcd(a, \gcd(b, k-1)) \mid c$ 即： $\gcd(a, b, k-1) \mid c$

---

八、样例验证

样例1：$a=3, b=9, c=5, k=10$
$\gcd(3, 9, 9) = \gcd(3,9) = 3$
$3 \nmid 5$ → No ✅

样例2：$a=7, b=3, c=1, k=10$
$\gcd(7, 3, 9) = \gcd(7,3) = 1$
$1 \mid 1$ → Yes ✅

---

九、算法步骤

对每组数据：

1. 计算 $g = \gcd(b, k-1)$
2. 计算 $d = \gcd(a, g)$
3. 如果 $d \mid c$，输出 Yes，否则输出 No

复杂度 $O(T \log M)$，其中 $M$ 是值域。

---

十、代码实现（C++）

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;
#define ll long long
#define file(A) freopen(A, "r", stdin)
#define mem(A, B) memset(A, B, sizeof(A))
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
inline ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}
inline ll p(ll a, ll k) {
    ll ans = 0;

    while (a) {
        ans += a % k;
        a /= k;
    }

    return ans;
}

int main(int argc, char *argv[]) {
    if (argc == 2 && !strcmp(argv[1], "local"))
        file("all.in");

    int T;
    ll a, b, c, k;
    scanf("%d", &T);

    while (T--) {
        scanf("%lld %lld %lld %lld", &a, &b, &c, &k);

        if (c % gcd(b, gcd(p(a, k), k - 1)) == 0)
            printf("Yes\n");
        else
            printf("No\n");
    }

    return 0;
}

---

十一、总结

本题的关键在于：

1. 利用 $k$ 进制数位和与数本身模 $k-1$ 同余的性质。
2. 将问题转化为线性同余方程的可解性问题。
3. 发现充要条件是 $\gcd(a, b, k-1) \mid c$。
4. 利用构造法证明充分性。。