专栏文章

数字存在性问题研究

江江湖午餐票
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min49k56
此快照首次捕获于
2025/12/01 20:19
3 个月前
此快照最后确认于
2025/12/01 20:19
3 个月前
查看原文

[ABC077D] Small Multiple

传送门

Problem

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

Solution

很容易发现答案必然小于或等于 KK 的数位累加和 f(K)f(K)，那么问题就转化为了是否存在一个数 xx，满足数位和为 r∈[1,f(K)]r\in[1,f(K)] 且 x≡0(modn)x \equiv 0 \pmod{n}，如果存在答案就是 rminr_{min}。
如果题目是这样的：
统计 [L,R][L, R] 中满足数位和等于 ss 且 x≡k(modm)x \equiv k \pmod{m} 的整数 xx 的个数。
熟悉吗？这就是很朴素的数位 DP。
有什么不同呢？
  • 本题不关心范围
  • 本题不关心个数
也就是说我们只关心能不能成功构造出一个数字，此时 pos 是无意义的，因为位置是无限的。所以我们只要记录当前的 state ——也就是数位和 sum 和余数 remainder，暴力加数转移即可。
使用 bfs 保证找到的一定是最小的数（没啥用就是了）。
C
#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

求满足以下两个条件的正整数 nn 的最小可能值：
  • nn 是 KK 的倍数。
  • nn 的十进制表示中包含 SS 作为子串。

Solution

答案必然为 aSbaSb 形式，且保证有一个解为 S×109+K−(S×109 mod K)S\times 10^9+K-(S\times 10^9\bmod K)，所以答案长度必然小于或等于 ∣S∣+9\left| S\right|+9。
由基本不等式得 min⁡(a,b)≤9999\min(a,b) \leq 9999，故我们可以枚举 aa 和 bb，并解出对应的 bb 和 aa。
这里有个细节，bb 的前导零是有意义的，所以我们还要枚举后缀长度 gg，因此 0≤b<10g0 \leq b < 10^g 来保证有前导零。
枚举 aa 时：
cur=(a⋅10∣S∣+S)⋅10g mod Kb≡−cur(modK),cur = (a\cdot10^{\left| S\right|}+S)\cdot 10^{g}\bmod K \newline b \equiv -cur\pmod{K}, \quad
显然 bmin=(K−cur) mod Kb_{min} = (K-cur)\bmod K。
枚举 bb 时：
cur=(S⋅10g+b) mod Ka⋅10∣S∣+g≡−cur(modK)cur=(S\cdot10^g+b)\bmod K \newline a\cdot10^{\left| S\right|+g}\equiv-cur\pmod K
这里要用扩展欧几里得算法求最小非负解 aa。
最后找最小的答案即可。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...