A1161 Forever (20 points)

数字题，dfs

1. 原文

“Forever number” is a positive integer A with K digits, satisfying the following constrains:

• the sum of all the digits of A is m;
• the sum of all the digits of A+1 is n; and
• the greatest common divisor of m and n is a prime number which is greater than 2.

Now you are supposed to find these forever numbers.

Input Specification

Each input file contains one test case. For each test case, the first line contains a positive integer N(≤5) . Then N lines follow, each gives a pair of K(3<K<10) and m(1<m<90) , of which the meanings are given in the problem description.

Output Specification

For each pair of K and m, first print in a line Case X, where X is the case index (starts from 1). Then print n and A in the following line. The numbers must be separated by a space. If the solution is not unique, output in the ascending order of n. If still not unique, output in the ascending order of A. If there is no solution, output No Solution.

Sample Input

2
6 45
7 80

Sample Output

Case 1
10 189999
10 279999
10 369999
10 459999
10 549999
10 639999
10 729999
10 819999
10 909999
Case 2
No Solution

2. 解析思路

使用暴力，但一定要在过程中进行判断，从而减少循环次数,及时剪枝

3. AC代码

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N, k, m, n;
bool flag;
//求最大公约数
int gcd(int a, int b)
{
    if (a%b == 0)
        return b;
    return gcd(b, a % b);
}
//判断是不是大于的素数
bool isPrime(int x)
{
    if (x <= 2)return false;
    for (int i = 2; i*i <= x; ++i)
        if (x%i == 0)return false;
    return true;
}
//数组化为整数
int getIndex(int a[])
{
    int num = 0;
    for (int i = 0; i < k; ++i)
    {
    	num =num*10+a[i];
    }
    return num;
}
bool check(int a)
{
    int b = a + 1;
    n = 0;
    while (b)
    {
        n += b % 10;
        b /= 10;
    }
    if (isPrime(gcd(m, n)))
        return true;
    else
        return false;
}
int num[20]={};
void dfs(int index, int digit, int sum)
{
	//不能超过k位，从0开始
    if (index >= k || sum > m)return;
    //if (sum + 9 * (k - index - 1) < m)return;//第index数字太小，以至于其他位数全部填9其和都达不到m
    num[index] = digit;
    if (sum == m && index == k - 1)//满足要求
    {
        int a = getIndex(num);
        if (check(a)){
        	flag = true;
            printf("%d %d\n",n,a);
        }
        return;
    }
    for (int i = 0; i < 10; ++i)
        dfs(index + 1, i, sum + i);
}
int main()
{
    scanf("%d\n",&N);
    for (int i = 1; i <= N; ++i)
    {
        scanf("%d%d\n", &k,&m);
        printf("Case %d\n", i);
        flag = false;
        for (int j = 1; j < 10; ++j){
            dfs(0, j, j);//第一位不能为0
        }
        
        if (flag==false)
        {
            printf("No Solution\n");
    	}
    }
    return 0;
}