【Codeforces 1120E】The very same Munchhausen
构造。
题目大意：
给定一个正整数 $a$。
定义 $S(x)$ 表示 $x$ 的各个数位上的数字之和。
要求找到一个正整数 $n$ 满足：
注意必须除尽。
输出任意一个答案。答案不能超过 $5\times 10^5$ 位。
不存在输出 $-1$。
题解：
题目中的式子相当于 $a\times S(a\times n)-S(n)=0$。
由于$a\leq 1000$，我们可以构造一个数 $n=b_1000b_2000b_3000\cdots$，设一共有 $k$ 个这样的 $b$。
那么相当于要求 $\sum\limits_{i=1}^k a\times S(a\times b_i)-S(b_i)=0$。
较为简单地，我们可以选择一个 $x$ 和一个 $y$ 满足：
当然如果直接找到恰好为 $0$ 的则可以直接输出。
假设我们找到了这样的两个数，那么我们显然可以将 $x$ 和 $y$ 分别重复若干次，使得它们的和为 $0$。
对于 $x$，容易发现 $x=1$ 就是一个不错的答案。我们考虑寻找靠谱的 $y$。
为了满足条件，我们想要使 $S(a\times y)$ 的值尽可能小，那么就希望 $a\times y$ 尽可能接近 $10^m$ 并且大于等于它。
我们就从 $m=1$ 开始逐渐递增，然后计算出 $y=\lceil\frac{10^m}{a}\rceil$，再对当前的 $y$ 进行验证即可。
$y$ 的值和 $S(y)$ 的值都可以递推，$S(a\times y)$ 的值也容易通过余数进行计算。
然后判一下最终长度是否不超过 $5\times 10^5$ 即可。
注意我们计算 $y$ 时存的是下取整的结果，如果遇到进位会比较麻烦，因此可以直接跳过进位的情况。
这样就可以找到满足条件的答案。如果 $m$ 枚举了非常大都无法找到答案，就可以认为无解。
在 $2\leq a\leq 1000$ 时都能输出正确答案。
Code：
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
string num;
int a;
inline int S(int n){
int k=0;
while(n)k+=n%10,n/=10;
return k;
}
int main(){
scanf("%d",&a);
if(a==1)return puts("1"),0;
int X=a*S(a)-1,k=1,nw=0;
while(k<a)k*=10;
for(;num.length()<200000;){
int dig=k/a;k%=a;
num+=(char)(dig^'0');
nw+=dig;
if(dig!=9||k==0){
int rest=(a-k)%a,sr=S(rest)+1;
if(rest)++dig,++nw,++num.back();
if(sr*a<=nw){
int Y=nw-sr*a;
if(Y==0){
puts(num.c_str());
return 0;
}
long long g=1LL*X*Y/__gcd(X,Y);
if(4*g/X+(num.length()+3LL)*(g/Y)<=499000){
for(int i=1;i<=g/X;++i)printf("1000");
for(int i=1;i<=g/Y;++i)printf("%s000",num.c_str());
return 0;
}
}
if(rest)--dig,--nw,--num.back();
}
k*=10;
}
puts("-1");
return 0;
}