Problem B
Super Number
Input: Standard Input

Output: Standard Output

Time Limit: 3 Seconds

Don't you think 162456723 very special? Look at the picture below if you are unable to find its speciality. (a | b means ‘b is divisible by a’)

Figure: Super Numbers

Given n, m (0 < n < m < 30), you are to find a m-digit positive integer X such that for every i (n <= i <= m), the first i digits of X is a multiple of i. If more than one such X exists, you should output the lexicographically smallest one. Note that the first digit of X should not be 0.

Input 

The first line of the input contains a single integer t(1 <= t <= 15), the number of test cases followed. For each case, two integers n and m are separated by a single space.

Output 

For each test case, print the case number and X. If no such number, print -1.

Sample Input                           Output for Sample Input

3 29

Problemsetter: Rujia Liu, Member of Elite Problemsetters' Panel

Special Thanks to:

Monirul Hasan (Alternate solution)

Shahriar Manzoor (Figure Drawing)

注意小細節, 2000+ms 通過

#include <stdio.h>
int find, n, m;
int N[50];
int div(int len, int j) {
    static int i, tmp;
    for(i = 1, tmp = 0; i < len; i++) {
        tmp = tmp*10 + N[i];
        tmp %= len;
    }
    tmp = tmp*10 + j;
    return tmp%len;
}
void dfs(int idx) {
    if(find)    return;
    int i, j = 1;
    if(idx == m+1) {
        find = 1;
        for(i = 1; i <= m; i++)
            printf("%d", N[i]);
        return;
    }
    for(i = (idx == 1); i < 10; i += j) {
        if(idx >= n && div(idx, i) == 0) {
            N[idx] = i;
            j = idx;
            dfs(idx+1);
        } else if(idx < n) {
            N[idx] = i;
            dfs(idx+1);
        }
    }
}
int main() {
    int t, cases = 0;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &m);
        printf("Case %d: ", ++cases);
        find = 0;
        dfs(1);
        if(!find)   puts("-1");
        else    puts("");
    }
    return 0;
}