附上详细题解,传送门：http://blog.csdn.net/lyy289065406/article/details/6698787/
大致题意：
给出2个整数n（n<10^100）和k（k<10000），求满足以下条件的整数m
1、m与n位数相同
2、m能被k整除
3、满足以上两点时，m和n在相同位置的地方，数字不同的个数最少
4、满足以上三点时，m值最小
收获：
1.寻解的有序性，第一次接触到有序的搜索，即在修改相同个数的情况下，从小的数开始搜索，满足题目要求。
2.一开始我认为搜索中的代码在变更m上的数字时是变更连续的几位，思考了一会后，发现for循环可以使得变更的数字在数位上是可以跳跃的。
3.把n的每一位放在数组中时，可以采取倒序存放，这样在搜索的时候利用同余公式比较方便。
4.在搜索中，从高位开始枚举比当前m小的数，和从低位枚举比当前m大的数，在搜索中呈现出了交替的搜索。这也是代码上值得学习的地方。
5.利用同余模公式，从高位开始向低位逐位求模。虽然本题没有用这种方法，但是也是一个收获。之所以不用上述方法，是因为搜索的时候改变的数位是可以跳跃的，而从高位开始向低位逐位求模则需要每一位连续着求。
6.递推求模:
定义数组mod[101][10]，mod[i][j]=((10^i)*j)%k，先求出：
0 1 2 3 4 5 6 7 8 9 （%k）
0 10 20 30 40 50 60 70 80 90 （%k）
0 100 200 300 400 500 600 700 800 900 （%k）
.....
通过递推式mod[i][j]=(mod[i-1][j]*10)%k; 就能避免n次方的运算，节省时间。
由此mod[][]就能组合出任意len(n)位内的整数对k求模后的值。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 105;
int k,len, mod[maxn][10], m[maxn];//mod[i][j]=((10^i)*j)%k
int flag[maxn][10005];//flag[pos][m_MODk]=RestNum
/*当搜索m的位置区间为[0,pos]，且当前数字串m对k取模值为m_MODk时，若剩下允许的修改数字的个数只允许修改RestNum个，则无论如何修改区间[0,pos]内的数字也无法使得m_MODk==0，那么对于同样的pos和m_MODk, 小于RestNum的个数则更加不可能了,这用于剪枝
*/
void init_mod()
{for(int i = 0; i <= 9; i++)mod[0][i] = i % k;for(int i = 1; i < len; i++)for(int j = 0; j <= 9; j++)mod[i][j] = (mod[i-1][j] * 10) % k;
}
bool dfs(int pos, int restnum, int m_modk)
{if(m_modk == 0)return true;if(restnum == 0 || pos < 0)return false;if(restnum <= flag[pos][m_modk]) //剪枝return false;for(int i = pos; i >= 0; i--) //枚举比n小的数m，且m要尽可能小，则从高位开始for(int j = 0; j < m[i]; j++){if(i == len-1 && j == 0) //m最高位不为0continue;int res = (m_modk - (mod[i][m[i]] - mod[i][j] + k) % k + k) % k;int tmp = m[i];m[i] = j;//i-1即缩减搜索区间if(dfs(i-1, restnum-1, res))return true;m[i] = tmp;}for(int i = 0; i <= pos; i++) //枚举比n大的数m，但m要尽可能小，则从低位开始for(int j = m[i]+1; j <= 9; j++){if(i == len-1 && j == 0) //m最高位不为0continue;int res = (m_modk + (mod[i][j] - mod[i][m[i]] + k) % k + k) % k; //同余模公式int tmp = m[i];m[i] = j;//i-1即缩减搜索区间if(dfs(i-1, restnum-1, res))return true;m[i] = tmp;}flag[pos][m_modk] = restnum; //在区间[0,pos]内只允许修改RestNum个数字无法使得m_MODk==0return false;
}
int main()
{char num[maxn];while(cin >> num >> k){int n_modk = 0; //n%klen = strlen(num);init_mod(); //打表mod[][]，利用同余模公式for(int i = 0; i < len; i++){m[i] = num[len-i-1] - '0';//倒序n，并转换为数字串，方便搜索时候的下标处理n_modk = (n_modk + mod[i][m[i]]) % k;}memset(flag, 0, sizeof(flag));for(int AllowNum = 1; AllowNum <= len; AllowNum++)//枚举允许修改的数字个数if(dfs(len-1, AllowNum, n_modk))//要保证搜索区间最大,所以搜索是有序的break;for(int i = len-1; i >= 0; i--)printf("%d", m[i]);printf("\n");}return 0;
}