这不是个BFS嘛。。一脸懵逼
先对输入的数字排序，就可以保证先生成出0的那个数字一定最小
最多5000种状态。。BFS秒过

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <string>
#include <map>
#include <cstring>
#include <ctime>
#include <vector>
#define inf 1e9
#define ll long long
#define For(i,j,k) for(int i=j;i<=k;i++)
#define Dow(i,j,k) for(int i=k;i>=j;i--)
using namespace std;
int n,m,a[101],q[10001],num[10001],nxt[10001],vis[10001],l=1,r,ans,tot,ANS[10001];
int main()
{
    scanf("%d%d",&n,&m);
    For(i,1,m)  scanf("%d",&a[i]);
    sort(a+1,a+m+1);
    For(i,1,m)  if(a[i]&&!vis[a[i]%n])  q[++r]=a[i]%n,vis[a[i]%n]=1,num[r]=a[i],nxt[r]=-1;
    while(l<=r)
    {
        int t=q[l];
        if(t==0){ans=l;break;}
        For(i,1,m)
        {
            int tmp=(t*10+a[i])%n;
            if(!vis[tmp])
                q[++r]=tmp,num[r]=a[i],nxt[r]=l,vis[tmp]=1;
        }
        l++;
    }
    while(ans!=-1)
    {
        ANS[++tot]=num[ans];
        ans=nxt[ans];
    }
    Dow(i,1,tot)    printf("%d",ANS[i]);
}
     

（a*b) mod c=(a mod c*b mod c) mod c

（a+b) mod c=(a mod c+b mod c) mod c

因此构图，一个余数对应一个点，对于每一个余数k,若(j*10+a[i]) mod n=l，则k与l连边，权为a[i]

求最短路即可

感谢吴豪..

令我恍然大虎..

``原来余数可以这样转换的..

好弱的数据..

我自己写了一组.

44440

10

44

88

242

52

24

346

241

254

123

褂掉..抱着试试的心态交上去..竟然..A了..

不用记录前面所有除过的数，只需要记录前面的余数。建一个图，图中的节点表示任意数除以n的余数，利用广搜，假设前一步的节点是x，那么下一步的节点就是（x*10+a[i]） mod n，两点间的权值是a[i]，那么从0出发，当走回0的时候，一路上的权值全部连起来，就是所求的数字。其核心思想就是利用余数代表前面的运算结果，避免记录和处理太大的数。注意针对余数进行判重。

=<
题目没说答案范围，我一开始估计是100位数字以内，结果总是WA第一个点，我以为第一个点是小数字的边界问题，结果开成500位就AC了。。

DP+按模分类

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
#define pos(x,y) (x+(y)*n)
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=1000000007;
const double eps=1e-8;

int n,m;
int a[20];
int f[510][10][5010];
int ten[510];
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n>>m;
    FOR(i,m) {
        int t;cin>>t;
        a[t]=1;
    }
    if (n<10) {
        FOR(i,9) {
            if (n*i<10&&a[n*i]) {
                cout<<n*i<<endl;
                return 0;
            }
        }
    }
    REP(i,0,9) if (a[i]) f[1][i][i%n]=1;
    ten[0]=1;
    FOR(i,500) ten[i]=ten[i-1]*10%n; 
    FOR(i,500) {
        REP(j,0,9) if (a[j]) REP(j2,0,9) if (a[j2]) {
            REP(k,0,n-1) {
                f[i+1][j2][(j2*ten[i]+k)%n]|=f[i][j][k];
            }
        }
    }
    REP(i,2,500) FOR(j,9) if (a[j]) {
        if (f[i][j][0]) {
            int s=j;
            cout<<s;
            int t=(n-(j*ten[i-1])%n)%n;
            int now=i-1;
            while (now) {
                REP(k,0,9) if (a[k]) {
                    if (f[now][k][t]) {
                        cout<<k;
                        t=(n+t-(k*ten[now-1])%n)%n;
                        break;
                    }
                }
                now--;
            }
            return 0;
        }
    }
    return 0;
}

#01: Accepted (364ms, 644KB)

#02: Accepted (367ms, 644KB)

#03: Accepted (102ms, 644KB)

#04: Accepted (106ms, 644KB)

#05: Accepted (94ms, 644KB)

#06: Accepted (110ms, 644KB)

#07: Accepted (121ms, 644KB)

#08: Accepted (129ms, 644KB)

#09: Accepted (129ms, 644KB)

#10: Accepted (145ms, 644KB)

Accepted / 100 / 1671ms / 644KB

o(n)的没秒杀？真心自卑了

Accepted 有效得分：100 有效耗时：9ms

这题用DP好啊~只是被那ansistring恶心到了,速度降了不少……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

1次秒杀 呵呵

核心代码

for j:=0 to n-1 do

if v then

for k:=1 to m do

begin

e:=(a[k]*x+j)mod n;

if not v then

begin

v:=true;

f:=a[k];

g:=j;

end else

if (a[k]0) then

if (a[k]

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

不幸 第299个通过 ……………………………………

太囧了，第一次竟然内存溢出...

我只能说，评测机太萎了，还好最后秒掉了...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

orz花了我二十分钟...

BFS解决~

不过DP确实没想出来,膜拜想出DP并写出来秒杀的牛们...

OTL...

楼下神牛：

BFS可以拿余数判重……所以也可以AC

不过我为啥202了？

我第一个点TLE/格式错误

其他90分……

真是无语……

我回楼下的。。。确实这样。。。

囧了。。。

谢谢。

要用高精吗

比较大小要从头比哦.不要像我一样犯低级错误..

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 9ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

呼呼，滚动数组太牛B了！

这10个十进制数字，有多少位啊？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

也就是说，是用以个数字（0，1，2....9）还是任意自然数啊？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

BFS万岁！

AC第一百题！

FT。BFS水题一次AC

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms