数字存在性问题研究

· · 个人记录

[ABC077D] Small Multiple

传送门

Problem

给定一个整数 K。求一个 K 的正整数倍 S，使得 S 的数位累加和最小。

Solution

很容易发现答案必然小于或等于 K 的数位累加和 f(K)，那么问题就转化为了是否存在一个数 x，满足数位和为 r\in[1,f(K)] 且 x \equiv 0 \pmod{n}，如果存在答案就是 r_{min}。

如果题目是这样的：

统计 [L, R] 中满足数位和等于 s 且 x \equiv k \pmod{m} 的整数 x 的个数。

熟悉吗？这就是很朴素的数位 DP。

有什么不同呢？

也就是说我们只关心能不能成功构造出一个数字，此时 pos 是无意义的，因为位置是无限的。所以我们只要记录当前的 state ——也就是数位和 sum 和余数 remainder，暴力加数转移即可。

使用 bfs 保证找到的一定是最小的数（没啥用就是了）。

#include <bits/stdc++.h>
using namespace std;
int k;
bool vis[100005][60];
void bfs() {
    queue<pair<int, int> > q;
    for(int i = 1; i <= 9; i++) {
        int remainder = i % k;
        int sum = i;
        if(!vis[remainder][sum]) {
            vis[remainder][sum] = true;
            q.push({remainder, sum});
        }
    }
    while(!q.empty()) {
        auto [remainder, sum] = q.front();
        q.pop();
        for(int i = 0; i <= 9; i++) {
            int new_remainder = (remainder * 10 + i) % k;
            int new_sum = sum + i;

            if(new_sum <= 55 && !vis[new_remainder][new_sum]) {
                vis[new_remainder][new_sum] = true;
                q.push({new_remainder, new_sum});
            }
        }
    }
}
int main() {
    cin >> k;
    bfs();
    for(int i = 1; i <= 55; i++) {
        if(vis[0][i]) {
            cout << i;
            break;
        }
    }
    return 0;
}

[ABC423G] Small Multiple 2

传送门

Problem

求满足以下两个条件的正整数 n 的最小可能值：

Solution

答案必然为 aSb 形式，且保证有一个解为 S\times 10^9+K-(S\times 10^9\bmod K)，所以答案长度必然小于或等于 \left| S\right|+9。

由基本不等式得 \min(a,b) \leq 9999，故我们可以枚举 a 和 b，并解出对应的 b 和 a。

这里有个细节，b 的前导零是有意义的，所以我们还要枚举后缀长度 g，因此 0 \leq b < 10^g 来保证有前导零。

枚举 a 时：

cur = (a\cdot10^{\left| S\right|}+S)\cdot 10^{g}\bmod K \newline b \equiv -cur\pmod{K}, \quad

显然 b_{min} = (K-cur)\bmod K。

枚举 b 时：

cur=(S\cdot10^g+b)\bmod K \newline a\cdot10^{\left| S\right|+g}\equiv-cur\pmod K

这里要用扩展欧几里得算法求最小非负解 a。

最后找最小的答案即可。