牛客周赛ROUND37--C题解

C-红魔馆的馆主(495倍数)

题意:

做法：dfs搜索后面添加的数字。

string ans="1000000000000000000";
void dfs(int cur,string addnum){     //用数字写的话会无限dfs，因为addnum永远等于0。
    if(cur==0){
        if(addnum.size()<ans.size()) ans=addnum;
        return;
    }
    if(addnum.size()>ans.size()) return;
    for(int i=0;i<=9;i++) dfs( (cur*10+i)%495,addnum+(char)('0'+i) );  //不能用stoll写，是因为这里取余了，不会爆long long。但是stoll会到达18+3位，会爆
}
void solve(){              //
    int n; cin>>n;
    if(n%495==0){
        cout<<"-1";
        return;
    }
    dfs(n,"");
    cout<<ans;
}