红魔馆的馆主

C-红魔馆的馆主_牛客周赛 Round 37 (nowcoder.com)

思路：dfs+剪枝优化。

注意：给的值可能是$10^{18}$，如果加一位LL超了。可以用取模操作来消除溢出影响，也许也可以用int128。

代码如下：

#include <bits/stdc++.h>
using namespace std;
int main()
{   
    using LL = long long;
    LL n; cin>>n;
    if(n % 495 == 0) {
        cout<<-1;
        return 0;
    }
    string ans(25, '9');
    auto dfs = [&](auto &&self,LL yu, string now) -> void {
        if(now.size() >= ans.size()) return ;
        if(yu == 0) {
            if(now.size() < ans.size()) ans = now;
            return ;
        }
        for(int i = 0; i < 10; ++i) {
            string tmp = now + char(i + '0');
            LL ny = (yu * 10 + i) % 495;
            self(self,ny, tmp);
        }
    };
    dfs(dfs,n % 495, to_string(n));
    cout<<ans.substr(to_string(n).size());
}