P2841A*B

· · 题解

麻烦管理员再审一下。

题目传送门：P2841

看到这道题要求最小值，首先想到的就是 \texttt{BFS} 。

思路：

从 1 开始，此后每次队尾进队头的 10 倍和 10 倍 加 1 。

由于最后的值一定很大，而我又不想写高精度。 并且 \texttt{BFS} 很浪费空间 ，所以肯定是要做优化的。

用模优化：

模的性质：如果 x \equiv y \pmod a ，则同时加减乘除后模 a 的余数仍然相同。

最后的值很大我们可以用 \texttt{string} 存储答案，中间作为运算过程的我们可以进行取模让计算规模减小。（整除相当于模后是 0 。）

同时我们可以弥补 \texttt{BFS} 很浪费空间的不足：

模完后相同的相当于一种状态，对于相同的状态，我们只要在队列中只需存储一个。（最多的时候也只有 10000 种状态。）

实现这个只需要开一个 \texttt{vis} 数组即可。

注意事项：

不要等入队了再判断 \texttt{vis} 里有没有，而是入队前就要判断。否则就像我一样：

代码：

#include<bits/stdc++.h>
using namespace std;
bool vis[10001];
queue<int> q;
queue<string> s;
int a;
string bfs(){
    q.push(1);
    s.push("1");
    vis[1]=1;
    while(1){//肯定找的到，所以while(1)
        string str=s.front();
        int x=q.front();
        q.pop();
        s.pop();
        if(!x)
            return str;
        vis[x]=1;
        if(!vis[x*10%a]){//入队前判断！！！
            q.push(x*10%a);
            s.push(str+"0");
        }
        if(!vis[(x*10+1)%a]){
            q.push((x*10+1)%a);
            s.push(str+"1");
        }
    }
}
inline void B(string x){//求B的，高精除
    for(int i=0;i<x.length();i++)
        x[i]-='0';
    int q=0;
    string ans="";
    for(int i=0;i<x.length();i++){
        q*=10;
        ans+=((q+x[i])/a)+'0';
        q=(q+x[i])%a;
    }
    int i;
    for(i=0;i<ans.length();i++)
        if(ans[i]!='0')
            break;
    for(;i<ans.length();i++)
        putchar(ans[i]);
}
int main(){
    cin>>a;
    string ans=bfs();
    B(ans);
    cout<<' '<<ans;
    return 0;
}

最后附上我的 \texttt{AC} 记录：