题目链接
题意：给出n到m的范围，求出一个数在前i位数组成的数字能被i整除。假设存在输出这个数，假设不存在。输出-1.
思路：回溯，每次放第i位，然后推断是否符合题意。这题踩着时间过去的2.6s（看了下别人的题解。能够降低取模次数来节省时间）。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int MAXN = 35;int arr[MAXN];
int n, m, flag;int mod(int d) {int sum = 0;for (int i = 0; i < d; i++) {sum = (sum * 10 + arr[i]) % d; }return sum;
}int dfs(int cur) {if (cur == m) return true; for (int i = 0; i <= 9; i++) {arr[cur] = i;if (cur < n - 1 || (cur >= n - 1 && !mod(cur + 1))) {if (dfs(cur + 1))return true;}} return false;
}int main() {int cas, t = 1;scanf("%d", &cas);while (cas--) {scanf("%d%d", &n, &m); flag = 0;for (int i = 1; i <= 9; i++) {arr[0] = i; if (dfs(1)) { flag = 1;break;}}printf("Case %d: ", t++);if (flag) {for (int i = 0; i < m; i++) printf("%d", arr[i]);printf("\n");}elseprintf("-1\n");}return 0;
}版权声明：本文博客原创文章，博客，未经同意，不得转载。
