Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Given a positive integer n, your task is to find a positive integer m, which is a multiple of n, and that m contains the least number of different digits when represented in decimal. For example, number 1334 contains three different digits 1, 3 and 4.

Input 

The input consists of no more than 50 test cases. Each test case has only one line, which contains a positive integer n ( 1n < 65536). There are no blank lines between cases. A line with a single `0' terminates the input.

Output 

For each test case, you should output one line, which contains m. If there are several possible results, you should output the smallest one. Do not output blank lines between cases.

Sample Input 

7 
15 
16 
101 
0

Sample Output 

7 
555 
16 
1111

---

題目描述：

找到一個用最少位數種類表示的十進制數字可以被 n 整除。
如果最少位數種類相同時，則選擇一個最小的數字。

題目解法：

根據離散數學，每個數字的倍數一定可以表示成由 0 和 1 構成的數字。
那麼可以保證最大上限的最少位數種類為 2。

根據題目意思，優先查找只能由 1 種構成的數字，採用查找循環節的 O(n) 算法。

當嘗試不出來時，開始窮舉湊成的 2 種構成，使用 BFS 的思路，只要優先對最小的拓展，
第一個查找出來的數字必然是由這 2 個數字構成的最小數字。

至於寫法有點不明確，但仍然得到 Accept。

稍微說明一下我的疑惑，假設兩個數字分別為 2 和 0，
數字開頭肯定是 20XXXXX...，但是對於 BFS 搜索時，會出現 220XXXX 是解。
由於我沒有額外檢查字典順序，可能在相同長度情況下 21XXXXX 會比較小 (接下來窮舉 2, 1)
此時輸出就會錯誤。


#include <stdio.h> 
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
int single(int d, int n) {
	int mark[65536] = {};
	int i = d%n, j = 1;
	if(i == 0)	return 1;
	for(j++; ; j++) {
		i = (i*10 + d)%n;
		if(i == 0)	return j;
		if(mark[i] == 1)	return -1;
		mark[i] = 1;
	}
}
char buffer[65536*2];
char ret[65536*2];
int combine(int d1, int d2, int n) {
	if((d1*10 + d2)%n == 0) {
		buffer[0] = d2, buffer[1] = d1;
		return 2;
	}
	int prev[65536][2][2] = {};
	int i, j, k, dd1 = min(d1, d2), dd2 = max(d1, d2);
	queue<int> q1, q2;
	q1.push((d1)%n), q2.push(d1 == dd2);
	prev[(d1)%n][d1 == dd2][0] = -1;
	while(!q1.empty()) {
		i = q1.front(), q1.pop();
		j = q2.front(), q2.pop();
		k = (i*10+dd1)%n;
		if(prev[k][0][0] == 0) {
			prev[k][0][0] = i, prev[k][0][1] = j;
			q1.push(k), q2.push(0);
		}
		k = (i*10+dd2)%n;
		if(prev[k][1][0] == 0) {
			prev[k][1][0] = i, prev[k][1][1] = j;
			q1.push(k), q2.push(1);
		}
		if(prev[0][0][0] || prev[0][1][0])
			break;
	}
	if(prev[0][0][0] == 0 && prev[0][1][0] == 0)
		return -1;
	//printf("%d %d %d %d\n", prev[0][0][0], prev[0][1][0], d1, d2);
	//getchar();
	int cnt = 0, pi, pj, idx = 0;
	i = 0;
	if(prev[0][0][0])	j = 0;
	else				j = 1;
	while(i != -1) {
		buffer[idx++] = j ? dd2 : dd1;
		cnt++;
		pi = prev[i][j][0];
		pj = prev[i][j][1];
		i = pi;
		j = pj;
		//printf("%d %d %d\n", idx, i, j);
		//getchar();
	}
	return cnt;
}
int main() {
	int n; /*
	freopen("in.txt","r+t",stdin);
    freopen("out.txt","w+t",stdout);*/
	while(scanf("%d", &n) == 1 && n) {
		int i, j, k;
		int mnlen = 0xfffffff, mnIdx = -1;
		for(i = 1; i <= 9; i++) {
			int f = single(i, n);
			if(f == -1)	continue;
			if(f < mnlen)
				mnlen = f, mnIdx = i;
		}
		if(mnIdx != -1) {
			for(i = mnlen-1; i >= 0; i--)
				putchar(mnIdx+'0');
			puts("");
			continue;
		}
		for(i = 1; i <= 9; i++) {
			for(j = 0; j <= 9; j++) {
				if(i == j)	continue;
				int f = combine(i, j, n);
				if(f == -1)	continue;
				if(f < mnlen) {
					mnlen = f;
					for(k = 0; k < mnlen; k++)
						ret[k] = buffer[k];
				}
			}
		}
		for(i = mnlen-1; i >= 0; i--)
			putchar(ret[i]+'0');
		puts("");
	}
	return 0;
}