题目大意：

给出一个数n，求m，使得m的长度和n相等。能被k整除。有多个数符合条件输出与n在每位数字上改变次数最小的。改变次数同样的输出大小最小的。 

共同拥有两种解法：DP解法，记忆化搜索的算法。

以后会更新记忆化搜索。

1、DP解法：

解题思路：

DP[i][j]表示数n的前i位除以k余j最小改变几位。

DP[len][0]就表示数n被k整除最小改变几位。

依据这个关系从后向前遍历DP数组能够找出全部满足条件的数的路径。

再依据关系从前往后输出。

以下是代码：

#include <stdio.h>

#include <string.h>

int dp[110][10005];

bool vis[110][10005];

int mod;

int min(int a,int b)

{

    if(a>b)a=b;

    return a;

}

int main()

{

    char s[105];

    while(scanf("%s %d",s,&mod)!=EOF)

    {

        memset(dp,0x3f3f,sizeof(dp));

        memset(vis,false,sizeof(vis));

        int len=strlen(s);

        /******特判部分↓*********/

        if(mod==1)

        {

            puts(s);

            continue;

        }

        if(len==1)

        {

            if((s[0]-'0')%mod==0)

            {

                puts(s);

            }

            else printf("%d\n",mod);

            continue;

        }

        /****DP部分  ↓******/

        for(int i=1; i<10; i++)

        {

            if(i==s[0]-'0')

            {

                dp[1][i%mod]=0;

            }

            else

            {

                dp[1][i%mod]=min(dp[1][i%mod],1);

            }

        }

        for(int i=1; i<len; i++)

        {

            for(int j=0; j<mod; j++)

            {

                if(dp[i][j]!=dp[104][0])

                {

                    for(int k=0; k<10; k++)

                    {

                        if(k==s[i]-'0')

                        {

                            if(dp[i+1][(j*10+k)%mod]>dp[i][j])

                            {

                                dp[i+1][(j*10+k)%mod]=dp[i][j];

                            }

                        }

                        else

                        {

                            if(dp[i+1][(j*10+k)%mod]>dp[i][j]+1)

                            {

                                dp[i+1][(j*10+k)%mod]=dp[i][j]+1;

                            }

                        }

                    }

                }

            }

        }

        /*****寻找路径部分    ↓******/

        vis[len][0]=true;

        for(int i=len-1; i>0; i--)

        {

            for(int j=0; j<mod; j++)

            {

                if(dp[i][j]!=dp[104][0])

                {

                    for(int k=0; k<10; k++)

                    {

                        if(vis[i+1][(j*10+k)%mod]&&((dp[i][j]==dp[i+1][(j*10+k)%mod]&&k==s[i]-'0')||(k!=s[i]-'0'&&dp[i][j]+1==dp[i+1][(j*10+k)%mod])))

                        {

                            vis[i][j]=true;

                            break;

                        }

                    }

                }

            }

        }

        /*****输出部分   ↓*******/

        int p=1,x=1;

        for(; p<10; p++)

        {

            if(vis[1][p%mod])

            {

                printf("%d",p);

                break;

            }

        }

        while(x<len)

        {

            for(int k=0; k<10; k++)

            {

                if(vis[x+1][(p*10+k)%mod]&&((s[x]-'0'==k&&dp[x][p]==dp[x+1][(p*10+k)%mod])||(s[x]-'0'!=k&&dp[x][p]+1==dp[x+1][(p*10+k)%mod])))

                {

                    printf("%d",k);

                    p=p*10+k;

                    p%=mod;

                    x++;

                    break;

                }

            }

        }

        puts("");

    }

    return 0;

}