Find The Multiple(DFS)

发布于 2020-09-03  0 次阅读


题目大意:

Find The Multiple
给你一个不超过200的数n
求一个数m,m为n的不为0的倍数且不超过200位

思路:

DFS,走∗ 10和∗ 10 + 1 两条路,在long long内有解

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=2e5 +9;
int n, flag;

void dfs(int x, int k){
    if(flag || k>=19)   return ;

    if(x%n==0){
        flag=1;
        cout<<x<<endl;
        return ;
    }
    dfs(x*10, k+1);
    dfs(x*10+1, k+1);
    return  ;
}

void solve(){
    while(cin>>n && n){
        flag=0;
        dfs(1,0);
    }
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    solve();
    return 0;
}

平平无奇的在校大学生