P143 Find The Multiple

按下面这种书上的写***超时。

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

void BFS(int n){
    queue<long long> myQueue;
    myQueue.push(1);
    while(!myQueue.empty()){
        long long now = myQueue.front();
        myQueue.pop();
        if(now % n == 0){
            printf("%lld\n", now);
            return ;
        }
        myQueue.push(10 * now);
        myQueue.push(10 * now + 1); 
    } 
}

int main(){
    int n;
    while(scanf("%d", &n) != EOF) {
        if(n == 0) break;
        BFS(n);
    }
    return 0;
}

改进：有除以n相同余数的只要遍历第一个就行，之后的可以直接跳过。
用visit[i%n]记录。
这样就不超时了，AC。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int MAXN=210;
bool visit[MAXN];

void BFS(int n){
    queue<long long> myQueue;
    myQueue.push(1);
    while(!myQueue.empty()){
        long long now = myQueue.front();
        myQueue.pop();
        if(!visit[now % n]){
            if(now % n == 0){
                printf("%lld\n", now);
                return ;
            }
            visit[now % n] = 1;
            myQueue.push(10 * now);
            myQueue.push(10 * now + 1); 
        }

    } 
}

int main(){
    int n;
    while(scanf("%d", &n) != EOF) {
        if(n == 0) break;
        memset(visit,0,sizeof(visit));
        BFS(n);
    }
    return 0;
}