yukicoder : No.2032 Let's Write Multiples!!

AtCoderよりfloor_sum登場頻度高くない？
https://yukicoder.me/problems/no/2032

問題

整数L,R,K,Cが与えられる。
L以上R以下のKの倍数をすべて書いた時、数字Cが書かれる回数を求めよ。

解法

各桁にCが何回出るかを考える。
下からd桁目がCの物は、下d桁がC000...～C999....となるものである。

これには、L≦nK≦Rを満たすnのうち、
(nK - C*10^(d-1))%(10^d)＜10^(d-1)
となるものを求める問題となる。
これは式変形するとfloor_sumを適用できる形となる。
あとはdごとに上記値を求めよう。

int T;
int L,R,K,C;

ll floor_sum(ll N,ll M,ll A,ll B) {
	// sum(i=0...N-1) floor((A*i+B)/M)
	
	ll ret=0;
	if(B>=M) ret+=N*(B/M), B%=M;
	if(A>=M) ret+=N*(N-1)/2*(A/M), A%=M;
	
	ll Y=(A*N+B)/M;
	if(Y==0) return ret;
	//floor(Y/M)に達するX
	ll X=Y*M-B;
	//Xの右側はY個ずつ
	ret+=(N-(X+A-1)/A)*Y;
	// 90度回転、Y=Nのラインは無視する
	ret+=floor_sum(Y,A,M,(A-X%A)%A);
	return ret;
}

ll hoge(ll v) {
	ll ret=0;
	ll N=v/K;
	ll cur=1;
	for(int d=0;d<9;d++) {
		ll LL=C*cur;
		ll RR=(C+1)*cur;
		ret+=floor_sum(N,cur*10,K,cur*10+K-LL)-floor_sum(N,cur*10,K,cur*10+K-RR);
		cur*=10;
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>L>>R>>K>>C;
		ll ret=hoge(R)-hoge(L-1);
		cout<<ret<<endl;
	}
}

まとめ

海外コンテストでfloor_sum相当出たことあるのかな。