UVA 10624 (13.11.27)

Super Number

Input: Standard Input

Output: Standard Output

Time Limit: 3 Seconds

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

Figure: SuperNumbers

Givenn, m (0 < n < m < 30), you are to find a m-digitpositive integer X such that for every i (n <= i <= m), thefirst i digits of X is a multiple of i. If more than onesuch 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 asingle integer t(1 <= t <= 15), the number of test cases followed.For each case, two integers n and m are separated by a singlespace.

Output

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

SampleInput Outputfor Sample Input

2

1 10

3 29

Case 1: 1020005640

Case 2: -1

Problemsetter:Rujia Liu, Member of Elite Problemsetters' Panel

Special Thanks to:

Monirul Hasan (Alternate solution)

Shahriar Manzoor (Figure Drawing)

有点小懒，就不说题意了。。。

然后直接给代码吧 不难的。。。

我就遇到一个问题：yes函数一开始想不到边取余边累积的方法，这是一点收获～

AC代码：

#include  
  
int n, m;  
char num[100];  
  
int yes(int k) {  
    int sum = 0;  
    for(int i = 0; i < k; i++)  
        sum = (sum * 10 + num[i]) % k;  
    return sum;  
}  
  
int dfs(int k) {  
    if(k == m)  
        return 1;  
    for(int i = 0; i < 10; i++) {  
        num[k] = i;  
        if(k+1 < n || (k+1 >= n && !yes(k+1))) {  
            if(dfs(k+1))  
                return 1;  
        }  
    }  
    return 0;  
}  
  
int main() {  
    int N, cas = 0;  
    scanf("%d", &N);  
    while(N--) {  
        scanf("%d %d", &n, &m);  
        int mark = 0;  
        for(int i = 1; i < 10; i++) {  
            num[0] = i;  
            if(dfs(1)) {  
                mark = 1;  
                break;  
            }  
        }  
        printf("Case %d: ", ++cas);  
        if(mark) {  
            for(int i = 0; i < m; i++)  
                printf("%c", num[i] + '0');  
            printf("\n");  
        }  
        else  
            printf("-1\n");  
    }  
    return 0;  
}