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 ofi. 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 

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)

题意：给定两个数字n，m；求一个长度为m的数字使得这个数字的任意前i(n=<i<=m)个数字组成的数能被i整数。

这道题按照我的思路就是回溯暴力。暂时没想到更好的方法了。

#include<iostream>
#include<cstring>

using namespace std;

int n,m,tag;
int arry[50];

int mod(int cnt)
{
    int sum=0;
    for(int i=0;i<cnt;i++)
    {
        sum=(sum*10+arry[i])%cnt;
    }
    return sum;
}

void dfs(int pos)
{
    if(pos==m)
    {
        tag=1;
        return;
    }
    if(tag) return;
    for(int i=0;i<=9;i++)
    {
        arry[pos]=i;
        if(pos<n-1||(pos>=n-1&&!mod(pos+1)))
        {
            dfs(pos+1);
            if(tag) return;
        }
    }
}

int main()
{
    int k;
    cin>>k;
    for(int t=1;t<=k;t++)
    {
        tag=0;
        cin>>n>>m;
        memset(arry,0,sizeof(arry));
        int i,j;
        for(i=1;i<=9;i++)
        {
            arry[0]=i;
            dfs(1);
            if(tag) break;
        }
        cout<<"Case "<<t<<": ";
        if(tag)
        {
            for(i=0;i<m;i++) cout<<arry[i];
        }
        else cout<<"-1";
        cout<<endl;
    }
    return 0;
}