Time Limit: 1 second

Memory Limit: 128 MB

【问题描述】

Sramoc（K,M）表示用数字0，1，2，。。。，K-1组成的自然数中能被M整除的最小数。给定K,M，求Sramoc（K,M）。

例如，K=2,M=7时，Sramoc（K,M）＝1001。

【输入格式】

输入文件第一行为两个整数K,M，满足2<=k<=10，1<=m<=1000。

【输出格式】

输出文件包含Sramoc（K,M）的值。

Sample Input

2 7

Sample Output

1001

【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t085

【题意】



按照数据,不一定要用满k个数字,可以只用一部分.

【题解】



这个用同余率来搞吧;

每次增加一位的时候只要知道前n-1位的模m的值就好了;

然后*10+新加上的数字然后再对m取模;就是n位数的模m值了;

然后可以用一个二维数组bo[i][j]来判重,表示最后一位数字为i,余数为j的情况有没有出现过;

用广搜吧；

加上那个判重;

很容易写出程序;

程序在队列的基础上写了个递归的输出过程;

这样就不用把整个数字都记录下来了(这个数字多大都没关系了);



【完整代码】

#include <cstdio>

#include <algorithm>

#include <cmath>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%I64d",&x)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int MAXN = 110;

struct abc

{

    int pre,num,last;

};

int k,m,l,r;

abc dl[500000];

bool bo[10][2000];

void output_ans(int now)

{

    if (now==0)

        return;

    output_ans(dl[now].pre);

    printf("%d",dl[now].last);

}

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    rei(k);rei(m);

    rep1(i,1,k-1)

    {

        if (i%m==0)

        {

            printf("%d\n",i);

            return 0;

        }

        if (bo[i][i%m]) continue;

        bo[i][i%m] = true;

        abc temp;

        temp.pre = 0;

        temp.num = i%m;

        temp.last = i;

        dl[++r] = temp;

    }

    l = 0;

    while (l < r)

    {

        abc tou = dl[++l];

        int now = tou.num;

        rep1(i,0,k-1)

        {

            int rest = (now*10+i)%m;

            if (!bo[i][rest])

            {

                bo[i][rest] = true;

                abc temp1;

                temp1.num = rest;

                temp1.pre = l;

                temp1.last = i;

                dl[++r] = temp1;

                if (rest==0)

                {

                    output_ans(r);

                    return 0;

                }

            }

        }

    }

    return 0;

}