C++11(clang++ 3.9) 解法, 执行用时: 65ms, 内存消耗: 4744K, 提交时间: 2019-11-09 10:20:53

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	while(cin>>n && n)
	{
		string ans = n-1 ? "" : "10";
		if(n > 1)
		{
			vector<int> hash[100100];
			for(int i = 1, flag = 1, r1 = 1, r; flag; r1 = (r1 * 10 + 1) % n, i++)
			for(int j = -9; j < 10; j++)
				if(j)
				{
					r = ((r1*j) % n + n) % n;
					if(r && i > 1 && j > 0 && hash[r].size())
						for(int k = 0; k < hash[r].size(); k++)
						{
							int digit = hash[r][k] % 100 - 9;
							int cnt = hash[r][k] / 100;
							int suffixd = j - digit;
							if(cnt < i && suffixd >= 0 && suffixd < 10)
							{
								string tmp;
								for(int kk = 0; kk < i; kk++)
									tmp += char((kk < i-cnt ? j : suffixd) + '0');
								if(tmp != to_string(n) && (ans == "" || tmp < ans))
									flag = 0, ans = tmp;
							}
						}
					hash[r].push_back(i*100+j+9);
				}		
		}
		printf("%d: %s\n", n, ans.data());
	}
}