## L2-056 被n整除的n位数

题目链接：https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=1913922872972247051&page=1

题目分析：这里如果个个遍历一定会超时，因为题目说了 a 和 b（1≤a≤b<10 ^15)，数据量是非常大的，所以这里我们不用遍历的方式来一个个判断，我们应该用**回溯+剪枝**来构造数字

```cpp
#include<bits/stdc++.h>
using namespace std;
//最终优化：回溯+剪枝，我们不判断数字，我们构造数字
typedef long long ll;
vector<ll> result;
int n;
ll a,b;
//当前前pos位组成的数
void dfs(int pos,ll current){
    if(current>b){
        return;
    }
    if(pos==n){
        if(current>=a){
            result.push_back(current);
        }
        return;
    }
    for(int d=0;d<=9;d++){
        ll next_num=current*10+d;
        if(next_num%(pos+1)==0){
            dfs(pos+1,next_num);
        }
    }
}
int main(){
    cin>>n;
    cin>>a>>b;
    //第一位不能从0开始
    for(int i=1;i<=9;i++){
        dfs(1,i);
    }
    sort(result.begin(),result.end());
    if(result.empty()){
        cout<<"No Solution"<<endl;
    }
    else{
        for(int i=0;i<result.size();i++){
            cout<<result[i]<<endl;
        }
    }
    return 0;
}