题解 P1602 【Sramoc问题】

吾王美如画 · 2019-08-10 16:10:03 · 题解

唔姆

（隔了好久没写过题解，可能不会写了23333）

• 首先看问题，利用0～k-1这k个数构成最小的可以整除m的数
• 接着我们就想到了暴搜，使用bfs每次往现有的数字后加一位，因为dfs的性质，所以最先找到的数一定是最小的。（显然这样是过不了的
• 但是我们可以发现 a\equivb(mod m)，那么显然a×10+c\equivb×10+c(mod m)。而我们又只需要最小的答案，所以当一个数的模数曾经出现过，我们就不需要这个数了。

根据上文我们得到这样一个代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int k,m;
int mod[15000];
queue<long long>q;
long long bfs(){
    while(!q.empty()){
        long long now=q.front();
        q.pop();
        for(int i=0;i<k;i++){
            long long to=now*10+i;
            if (mod[to%m]==0){
                mod[to%m]=1;
                q.push(to);
                if (to%m==0)return to;
            }
        }
    }
}
int main(){
    cin>>k>>m;
    for(int i=1;i<k;i++){
        q.push(i);
        mod[i%m]=1;
    }
    if (k==2&&m==999)printf("111111111111111111111111111");
    else cout<<bfs();
    return 0;
} 

因为最后一个点超大，所以longlong也会爆。（我看好多人都这样直接打表过的

所以我们进一步想，由之前提到的a\equivb(mod m)而a×10+c\equivb×10+c(mod m)，我们没有必要把整个数放入队列，只需放对m的模数就ok，最后为了输出，保存每个数的father和这时选的是哪个数，反向输出就OK。

（代码完全体

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int k,m;
int mod[15000],fa[15000],which[15000];
queue<int>q;
void out(int now){
    if (now==-1)return;
    out(fa[now]);
    cout<<which[now];
}
void bfs(){
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i=0;i<k;i++){
            int to=(now*10+i)%m;
            if (mod[to]==0){
                mod[to]=1;
                which[to]=i;
                fa[to]=now;
                q.push(to);
                if (to==0){
                    out(to);
                    return;
                }
            }
        }
    }
}
int main(){
    cin>>k>>m;
    memset(fa,-1,sizeof(fa));
    for(int i=1;i<k;i++){
        q.push(i%m);
        mod[i%m]=1;
        which[i%m]=i;

    }
    bfs();
    return 0;
}