牛客周赛 Round 37 C.红魔馆的馆主

非常恶心的诈骗，手玩了半小时，发现了一堆规律，比如是11的倍数的偶数数位和奇数数位要相等

还搞上了逆元，是5的倍数必须0 or 5结尾，是9的倍数必须数位之和是9的倍数结果做不出来

然后不是构造是纯纯的暴搜 直接暴力看余数就好了，但是我好菜 觉得有点玄学～

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
const int N = 1e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;int n,x;
string t;
string ans="10000000000000000000";
void dfs(int u,string t){if(!u){if(t.size()<ans.size())ans = t;return;}if(t.size()>ans.size())return;for(int i=0;i<=9;++i){dfs((u*10+i)%495,t+(char)(i+'0'));}}void solve()
{cin>>n;n%=495;if(n%495==0){cout<<-1;return;}else dfs(n,"");for(char &c:ans)cout<<c;}signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _;//cin>>_;_ = 1;while(_--)solve();return 0;
}