首页 > itarticle > poj

poj

admin 11月 13, 2020 0

题目链接

题意：

给一个数n，让你找出一个只有1，0，组成的十进制数，要求是找到的数可以被n整除

题解：

用DFS是搜索当前位数字（除最高位固定为1），因为每一位都只有0或1两种选择

AC代码：


#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef unsigned long long ll;
const int maxn=230;
int n;
bool found;
void (ll ans,int k){
    if(found)return;
    if(ans%n==0){
        printf("%llun",ans);
        found=1;
        return;
    }
    if(k==19)return;
    dfs(ans*10,k+1);
    dfs(ans*10+1,k+1);
}
int main(){
    while(scanf("%d",&n)&&n){
        found=0;
        dfs(1,0);
    }
    return 0;
}