kmjp's blog

競技プログラミング参加記です

ゆるふわ競プロオンサイト #3 : Digit Sum Multiple

なんか似たようなの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:
		;
	}
}

まとめ

これ確かに配点難しいな。