なんか似たようなのCFで見たことあるような気もするが。
https://www.hackerrank.com/contests/yfkpo3-1/challenges/digit-sum-multiple
問題
整数Nが与えられる。
以下を満たす整数を1つ答えよ。
- N桁であり、各桁非0である。
- s(N)を各桁の総和とすると、Nはs(N)の倍数である。
解法
s(N)は高々O(N)なので、桁数に対しあまり大きくない。
よってs(N)の倍数を考えると、上の桁はほとんど1であるようなものは必ず作れる。
(10^d>s(N)であるdがあれば、d桁より上が全部1であるものは必ず作れる)。
今適当に作った数が11111....111111XYZとし、その総和をMとする。
仮にどこかの桁を1だけ増やすとそれにより総和(M+1)で割った余りも変化する。
この時、(M+1)が素数であるならば、Nは(M+1)に近いのでかなりの高確率でどこかの桁で余りが0になるようなものに遭遇することが見込める。
ここまでくるとあとは容易。
下数桁を総当たりし、その際「あと1桁インクリメントしたときに余りを0にできるか?」を考えると、下数桁の総当たりはいくつか試すだけで(総和が素数になって)ヒットすることが期待できる。
int T; int M; void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>M; for(i=1;;i++) { int d=0; int sum=0; x=i; while(x) { d++; sum+=x%10; if(x%10==0) { d=-1; break; } x/=10; } if(d<0) continue; int md=M+sum-d+1; ll r=0; FOR(j,M-d) r=(r*10+1)%md; FOR(j,d) r=(r*10)%md; r=(r+i)%md; ll p10=1; FOR(j,M) { if((r+p10)%md==0) { string S(M-d,'1'); S+=to_string(i); S[M-1-j]++; cout<<S<<endl; goto out; } p10=p10*10%md; } } out: ; } }
まとめ
これ確かに配点難しいな。