头文件比代码还长||POJ1426

发布于 2020-04-01  1917 次阅读


题意

给定一个正整数n,请编写一个程序来寻找n的一个非零的倍数m,这个m应当在十进制表示时每一位上只包含0或者1。你可以假定n不大于200且m不多于100位。
提示:本题采用Special Judge,你无需输出所有符合条件的m,你只需要输出任一符合条件的m即可。

题解

无脑dfs就行啦

long long可以过


#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <cstdio>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ll;
ll ans[300];
void dfs(int n,ll cnt,int t)
{
    if(t>19||ans[n])return;
    if(cnt%n==0)
    {
        ans[n]=cnt;
        return;
    }
    dfs(n,cnt*10,t+1);
    dfs(n,cnt*10+1,t+1);
}
int main()
{
    int n;
    while(cin>>n)
    {
        dfs(n,1,1);
        cout<<ans[n]<<endl;
    }
    return 0;
}

Humble Halten