1136.cpp

zoj 1136题。 BFS搜索+同余求解

#include <string>
#include <cstdio>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;

map<int,bool> flagmap;
queue<string> thequeue;
bool exitflag=false;
int num[10];

void itoa(long long val,char *str)
{
    int i=0;
    if(val==0)
        strcpy(str,"0");
    else
    {
        while(val)
        {
            str[i]=val%10+'0';
            val/=10;
            i++;
        }
        str[i]='\0';
        int len = strlen(str);
        for(int i=0;i<len/2;i++)
        {
            swap(str[i],str[len-1-i]);
        }

    }
}

string Head_zero_remover(string num)	// 化简“”等数
{
	if(num[0] != '0')
		return num;
	int pos=num.find_first_not_of('0');
	if(pos == string::npos)	// string::npos -1 没找到
		return "0";
	return num.substr(pos, num.size()-pos);
}

string MSDiv(string x, int y, int &res)  //模拟竖式除法
{
	string quot(x.size(), 0);

	res=0;
	for(int i=0; i<x.size(); ++i)
	{
		res = 10*res+x[i]-'0';
		quot[i] = res/y+'0';	// 整除结果为商
		res %= y;	// 取余保留
	}
	return Head_zero_remover(quot);
}


int main()
{
    string notstr,str;
    char tempstr[10]="";
    int n=0,m,rest=0;
    char c;
    while(scanf("%d",&n)!=EOF)
    {
        strcpy(tempstr,"");
        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {
            scanf("%d",&num[i]);
        }
        sort(num,num+m);
        if(n==0)
        {
            printf("0\n");
            exitflag=true;
        }
        else
        {
            for(int i=0;i<m;i++)
            {
                if(num[i]!=0)
                {
                    char c =num[i]+'0';
                    str.assign(1,c);
                    thequeue.push(str);
                }
            }
            while(thequeue.size()) //BFS
            {
                str=thequeue.front();
                thequeue.pop();
                MSDiv(str,n,rest);
                if(rest==0)
                {
                    printf("%s\n",str.c_str());
                    exitflag=true;
                    break;
                }
                if(flagmap[rest]!=true)
                {
                    flagmap[rest]=true;
                    for(int i=0;i<m;i++)
                    {
                        notstr.assign(str);
                        notstr+=(num[i]+'0');
                        thequeue.push(notstr);
                    }
                }
            }

        }
        if(exitflag==false)
        {
            printf("0\n");
        }
        exitflag=false;
        while(thequeue.size())
            thequeue.pop();
        flagmap.clear();
    }

}