(旧存档) 杭电多校第六场-I题

I 数学

题意

给你一个 $b$ 和 $x$，问你什么时候：$\forall y, x$ | $sum(y) \rightarrow x$ | $y$，其中 $sum(y)$ 代表 $b$ 进展下的数位和。

思路

对于 $∀ y = (c_1c_2…c_n)_b$, 那么有：

$x$ | $\sum c_i \rightarrow x$ | $\sum b^ic_i$

我们在右方凑出 $\sum c_i$，那么有：

$x$ | $\sum c_i \rightarrow x$ | $(\sum(b^i-1)c_i + \sum c_i)$

只需:

$x$ | $\sum(b^i-1)c_i$

即只需:

$x$ | $(b^i-1) \leftrightarrow x$ | $(b-1)(b^{i-1}+…+b^1+1)$

因此，只需:

$x$ | $(b-1)$

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        ll b, x;
        scanf("%lld%lld", &b, &x);
        printf("%c\n", "FT"[(b - 1) % x == 0]);
    }
    return 0;
}