首先，要说明的是本体的解体思路诚如刘汝佳所说有两种；
第一种 ， 定义d（i,j）为i根火柴拼出的模m余数为j的最大数，来更新d(i + c(k),(j*10+k)%m );（为什么不递推而使用更新刷表法，因为尝试从i，j直接转移到其子状态,j的模不好计算）
这种算法状态数和转移次数都不错，但必须使用大数，会超时；
第二种，使用d（i，j）表示i位数模m为j最少需要多少火柴（特别注意状态转移时，当i >1时不能有前导零，有前导零会不划算，不如把它放后面）； 通过该状态可计算出一个火柴数最多可表示成几位数；
算出位数之后，需要计算的是尝试从高位到低位依次枚举较大值，设 m=7，最大数为三位数，比如第一位假设为9 ，则d（2，3）+c（9）<=n;则第一位可放置9，依次枚举即可得到最大值； 注意这里的d（i，j）又可以有前导零了，即使全为0构成也可以；（我的做法就是有重新按可有前导零dp了一下）
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 100000
const int maxn = 100 + 5;
const int maxm = 3000 + 50;
const int c[10]={6,2,5,5,4,5,6,3,7,6};
int d[55][maxm],n,m;
int yu[10][55];
int lim = 54,wei,comefrom;
void init(){
for(int i=1;i<=9;i++) yu[i][1]=i%m;
for(int i=1;i<=9;i++)
for(int j=2;j<55;j++)
yu[i][j]=(yu[i][j-1]*10)%m;
}
int pre_dp(){
for(int i=0;i<=lim;i++)
for(int j=0;j<=m;j++)
d[i][j]=INF;
for(int i=0;i<=m;i++){
for(int j=9;j>=1;j--){
if(j%m==i){
if(d[1][i]>c[j]){
d[1][i]=c[j];
}
}
}
}
for(int i=1;i<lim;i++)
for(int j=0;j<=m;j++){
for(int k=0;k<=9;k++){
d[i+1][(j*10+k)%m]=min(d[i+1][(j*10+k)%m],d[i][j]+c[k]);
}
}
wei=-1;
for(int i=lim;i>=1;i--){
if(d[i][0]<=n){
wei=i; break;
}
}
}
void back_dp(){
for(int i=0;i<=lim;i++)
for(int j=0;j<=m;j++)
d[i][j]=INF;
for(int i=0;i<=m;i++){
for(int j=9;j>=0;j--){
if(j%m==i){
if(d[1][i]>c[j]){
d[1][i]=c[j];
}
}
}
}
for(int i=1;i<lim;i++)
for(int j=0;j<=m;j++){
for(int k=0;k<=9;k++){
d[i+1][(j*10+k)%m]=min(d[i+1][(j*10+k)%m],d[i][j]+c[k]);
}
}
}
void solve(){
pre_dp();
if(wei==-1){
if(n>=6) printf("0\n");
else printf("-1\n"); return ;
}
back_dp();
vector<int> ans;
int temp = n,pre=0;
for(int i=wei;i>=1;i--){
for(int j=9;j>=0;j--){
if(i>1){
if(c[j]+d[i-1][(m+pre-yu[j][i])%m]<=temp){
ans.push_back(j);
pre=(m+pre-yu[j][i])%m;
temp-=c[j];
break;
}
}
else {
if(c[j]<=temp&&j%m==pre){
ans.push_back(j); break;
}
}
}
}
int all=0,M=0,mi=1;
for(int i=0;i<ans.size();i++){
printf("%d",ans[i]);
all+=c[ans[i]];
M=(M+ans[i]*mi)%m;
mi=mi*10%m;
} printf("\n");
}
int main()
{
int kase=1;
while(scanf("%d",&n)==1&&n){
scanf("%d",&m);
init();
printf("Case %d: ",kase++);
solve();
}
return 0;
}