求一个K进制下是N的倍数的数，要求这个数使用的数字最少，数字个数相同时取较小的数。
首先有一个结论，至多用两个数字可以构造任意数的倍数。假设只有一个数字吗，由这一个数字构成的数模N的结果只能是0~N-1，由抽屉原理可知必然存在两个数模N的结果相同，这两个数一减，结果有两个数字构成，模N的结果是0。
然后就暴力BFS吧，队列中存的是余数，找到余数为0或者出现已经出现过的余数就返回。每次找到解比较跟新一下即可。
1 #include <string.h> 2 #include <stdio.h> 3 #define MAXN 10005 4 int n, k, num[2]; 5 int vis[MAXN], fa[MAXN], q[MAXN], front, rear; 6 char st[MAXN], ans[MAXN], str[MAXN]; 7 int bfs(int nums) 8 { 9 memset(vis, 0, sizeof vis); 10 q[front = rear = 0] = 0, rear++; 11 while (front < rear) { 12 int u = q[front++]; 13 for (int i = 0; i < nums; i++) { 14 int v = (u * k + num[i]) % n; 15 if (!vis[v] && !(u == 0 && num[i] == 0)) { 16 fa[v] = u, st[v] = num[i] + '0'; 17 vis[v] = 1; 18 if (v == 0) return 1; 19 else q[rear++] = v; 20 } 21 } 22 } 23 return 0; 24 } 25 bool cmp(char *a, char *b) { 26 int lena = strlen(a), lenb = strlen(b); 27 if (lena != lenb) return lena < lenb; 28 for (int i = 0; i < lena; i++) { 29 if(a[i] != b[i]) return a[i] < b[i]; 30 } 31 return 0; 32 } 33 int len = 0; 34 void getstr(int u) { 35 if (fa[u] != 0) getstr(fa[u]); 36 str[len++] = st[u]; 37 } 38 void updateans() { 39 len=0; getstr(0); str[len] = '\0'; 40 if (strcmp(ans, "a") == 0 || cmp(str,ans)) strcpy(ans, str); 41 } 42 int main() { 43 //freopen("test.in","r",stdin); 44 while (scanf("%d%d", &n, &k) != EOF) { 45 strcpy(ans, "a"); 46 for (int i = 1; i < k; i++) 47 if (num[0] = i, bfs(1)) updateans(); 48 if(strcmp("a", ans) == 0) { 49 for(int i = 0; i < k; i++) 50 for(int j = i+1; j < k; j++) 51 if(num[0] = i, num[1] = j, bfs(2)) updateans(); 52 } 53 printf("%s\n",ans); 54 } 55 return 0; 56 }