[原创]CA Academy 0-K Multiple [bfs，记录路径]【思维建图】

Tabris

CSDN思维各OJ

发布于：2017年8月10日

次浏览

[原创]CA Academy 0-K Multiple [bfs，记录路径]【思维建图】

2017-08-10 11:26:27 Tabris_ 阅读数：370

博客爬取于 2020-06-14 22:39:29
以下为正文

版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/77044181

题目链接：https://csacademy.com/contest/archive/task/0-k-multiple/solution/

————————————————————————————————————————

0-K Multiple
Time limit: 1000 ms
Memory limit: 128 MB

You are given an integer N and a digit K. Find the smallest multiple of N that consists only of digits K and $0$.

Standard input
The first line contains two integers NN and KK.

Standard output
Print the result on a single line.

Constraints and notes
$1 \leq N \leq 10^5,1 \leq K \leq 9$

Input
5 2
Output
20

Input
7 4
Output
4004

Input
13 7
Output
7007
————————————————————————————————————————

题意：
给你一个数 N 和一个数字 K

让你找到一个最小的有 K 和 0 组成的数字，能被 N 整除

解题思路：

对于这个数字能确定第一位一定是 K,
有了下一位 就是 K*10+0/K 了，

这种操作下出现的所有数字对 N 取模依然会有一个结果，且不超过 N 的。且最后一定有一个是 %N 为 0 的。这种情况就是答案了，

所以我们可以的枚举 K*10+0/K 这样的数来计算，但是注意题目要求的是最小的，

这时候有 我们可以类似于建立一个有向图

然后 bfs 下去就好了，先处理 0，在处理 k，这样到达每个 %N 的位置均能保证最小，然后处理一个数组记录下路径就好了

附本题代码
————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

int n,k;
int d[N],f[N],c[N];
int main(){
    while(cin>>n>>k){

        for(int i=0;i<=n;i++) d[i]=INF;

        queue<int>q;
        q.push(k%n);
        d[k%n]=1;
        c[k%n]=k;
        f[k%n]=-1;
        while(!q.empty()){
            int t = q.front();q.pop();
            int tem = (t*10)%n;
            int tmp = (t*10+k)%n;
            if(d[tem]==INF){
                d[tem]=d[t]+1;
                c[tem]=0;
                f[tem]=t;
                q.push(tem);
            }
            if(d[tmp]==INF){
                d[tmp]=d[t]+1;
                c[tmp]=k;
                f[tmp]=t;
                q.push(tmp);
            }
        }
        string s = "";
        int x = 0;
        while(x>=0){
            s+=(char)('0'+c[x]);
            x=f[x];
        }
        reverse(s.begin(),s.end());
        cout << s<< "\n";
    }
    return 0;
}

本页文档最后更新于：2021年5月16日

CSDN