题解 P2841 【A*B Problem】

· · 题解

没看懂下面的题解...

这题，求01串很简单，bfs01串，每次向后扩展一位，然后由同余，可以直接算出01串对A的余数，如果bfs顺序是先0再1的话，一旦发现一个余数是0的，那么01串一定最小。

具体转移过程可以这样看：(a是01串，m是此01串的余数)

$ m=(m*10+1$(或0)$)modA

以上两个可以用struct存储。剩下就是bfs了。

至于简直，由于两个01串余数相同时，选小的和选大的对找到整除的答案无影响，但是选小的肯定优于选大的，这时候就可以直接剪掉，不继续搜索这个01串的可行方案了。

最后是高精度除法，高精除单精很好想，不难写。

代码：

#include <bits/stdc++.h>
using namespace std;

int x;

bool b[10006];

struct ha
{
    int a[106];
    int m;
    int len;
};

queue<ha> p;

void chu(ha v)
{
    int head=1;
    int pp=0;

    while(head<=v.len)
    {
        while(pp<x&&head<=v.len)
        {
            pp=pp*10+v.a[head];
            head++;
        }
        printf("%d",pp/x);
        pp=pp%x;
    }
    printf(" ");
}

int main()
{
    scanf("%d",&x);

    ha first;
    first.a[1]=1;
    first.len=1;
    first.m=1;
    p.push(first);

    while(!p.empty())
    {
        ha now=p.front();
        p.pop();
        b[now.m]=1;
        if(now.m==0)
        {
            chu(now);
            for(int i=1;i<=now.len;i++)
                printf("%d",now.a[i]);
            printf("\n");

            return 0;
        }
        now.len++;
        now.a[now.len]=0;
        int lins=now.m;
        now.m=(now.m*10)%x;
        if(b[now.m]==0)
        {
            b[now.m]=1;
            p.push(now);
        }
        now.a[now.len]=1;
        now.m=(lins*10+1)%x;
        if(b[now.m]==0)
        {
            b[now.m]=1;
            p.push(now);
        }
    }


    return 0;
}