题解 P2841 【A*B Problem】

· · 题解

看到这道题，我的第一想法就是暴力枚举01串，再判断这个数是否能被 a 整除。

显然，这样的暴力枚举会超时，因为会有大量重复状态。

当一个数能被 a 整除，说明这个数 \mod a = 0 。

所以当两个数分别为 x 和 y 并且 x \equiv y \pmod{a} 时， x 和 y 就重复了，因为在它们两个后面同时加上 1 或 0 ，它们的余数也都一样，因为我们要求的是最小的答案，所以我们要舍去较大数。

当然，求最小数，我们首选bfs算法，因为先入队列的一定是较小的数字，我们只要用一个 vis数组判断余数是否重复。

于是求出01串的时间复杂度就为 O(n) 。

然后我们要求这个01串除以 a 的商，直接模拟一下即可。

#include<bits/stdc++.h>
using namespace std;
int n,vis[55000];
//n为题目中的A
int sum,len;
string ans;
queue<pair<string,int> > q;
//string 存01串，int 存除以n的余数
void bfs(){
    q.push(make_pair("1",1));
    vis[1]=1;
    while(!q.empty()){
        string s=q.front().first;
        int mo=q.front().second;
        q.pop();//bfs常规操作
        if(mo==0){
            ans=s;
            break;
        }//当余数为0，保存答案，直接退出循环（bfs第一个即为最小值）
        if(vis[mo*10%n]==0){
            vis[mo*10%n]=1;
            q.push(make_pair(s+"0",mo*10%n));
        }//后面加个0
        if(vis[(mo*10+1)%n]==0){
            vis[(mo*10+1)%n]=1;
            q.push(make_pair(s+"1",(mo*10+1)%n));
        }//后面加个1
    }
}
int main(){
    scanf("%d",&n);
    bfs();
    len=ans.size();
    for(int i=0;i<len;++i){
        sum=sum*10+ans[i]-'0';
        if(sum>=n){
            printf("%d",sum/n);
            sum=sum%n;
        }
    }//高精除法，因为01串已经是n的倍数，所以很简洁
    cout<<" "<<ans<<endl;
    return 0;
}